Divide and Conquer recurrences are mathematical equations. It describes the time complexity of divide-and-conquer algorithms. Divide and conquer is a problem-solving technique to solve a big problem by breaking down it into smaller subproblems. And this smaller subproblem is then solved independently to find the solution for the original problem. After solving these subproblems, we combine them to find the solution to the original problem.
In other words, we can also explain that the algorithm is called divide and conquer because it divides the problem into smaller subproblems and later combines the solution of each subproblem to reach the solution of the main/original problem. This process of reaching the solution to the main problem is done using recursion. The problem function calls itself recursively until the base condition is reached. The running time of such algorithms is described using recurrence equations.
Time complexity analysis of divide and conquer algorithms requires recurrence relations. This recurrence relations equation expresses the running time of an algorithm in terms of the running time on smaller input sizes n.
Divide and Conquer Recurrence Relation
T(n) = a * T(n/b) + f(n)
Where:
- T(n) – Time complexity of the algorithm on an input of size n.
- a – Number of subproblems.
- n/b – Size of each subproblem.
- f(n) – Time complexity of any additional work done outside the recursive calls.
Divide and Conquer involves three main steps
- Divide: Break the problem into smaller subproblems of the same type.
- Conquer: Solve these subproblems, usually recursively.
- Combine: Merge the solutions of the subproblems to solve the original problem.
This method reduces the complexity of solving big problems by focusing on smaller, easier-to-solve pieces.
Example to understand the concept of divide and conquer recurrences
Fibonacci Series Numbers
The Fibonacci series generates a sequence of numbers where each number is obtained by the sum of its two preceding numbers. However, we can compute Fibonacci numbers using a divide-and-conquer approach.
Recurrence relation for computing the nth Fibonacci number:
T(n) = T(n-1) + T(n-2) + O(1)
In the above example
- T(n) – The time complexity of computing the nth Fibonacci number.
- (n-1)th and (n-2)th – The algorithm recursively computes the (n-1)th and (n-2)th Fibonacci numbers and then adds them together.
- (O(1)) – The additional work done outside the recursive calls is the constant time operation of addition (O(1)).
This recurrence relation describes the time complexity of computing Fibonacci numbers.
Examples of Divide and Conquer Recurrences
- Binary Search: This is a method to find an item in a sorted list. First, we divide the list into two halves. We then determine in which half the item would be, if it’s there at all. We keep dividing the half where the item could be until we find the item or conclude it’s not there. This process can be described by the recurrence relation T(n) = T(n/2) + c, where T(n) is the time to search in a list of n items, and c is the constant time to do the division and comparison at each step.
- Merge Sort: This algorithm sorts a list by dividing it into two halves, sorting each half, and then merging the sorted halves. The sorting of each half is done recursively using the same divide-and-conquer approach. The recurrence relation for merge sort is T(n) = 2T(n/2) + cn, where T(n) is the time to sort a list of n items, and cn represents the time to merge the two sorted halves.
Important Points
- Recurrence Relations: These are equations that define sequences of numbers. In the context of divide and conquer, they help us understand how the time or space requirements of an algorithm grow as the size of the input increases.
- Solving Recurrences: Techniques like the Master Theorem can be used to find closed-form solutions to recurrence relations, giving us a clear understanding of an algorithm’s efficiency.
- Example with Real-life Analogy: Imagine a large family photo that needs to be cut into individual pictures. Instead of cutting each person out one by one, you could divide the photo into halves, then quarters, and so on, until each person’s picture is separated. This “divide and conquer” approach simplifies the task, similar to how algorithms tackle complex problems.
Conclusion
Divide and Conquer is a powerful strategy in computer science for solving problems efficiently. By breaking down a large problem into smaller parts, solving those parts, and then combining the solutions, complex tasks become more manageable.