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.
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.