A divide and conquer algorithm is a strategy of solving a large problem by
To use divide and conquer algorithms, recursion is used. Learn about recursion in different programming languages:
Here are the steps involved:
Let us understand this concept with the help of an example.
Here, we are going to sort an array using the divide and conquer approach (ie. merge sort).
The complexity of the divide and conquer algorithm is calculated using the master theorem.
T(n) = aT(n/b) + f(n), where, n = size of input a = number of subproblems in the recursion n/b = size of each subproblem. All subproblems are assumed to have the same size. f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions
Let us take an example to find the time complexity of a recursive problem.
For a merge sort, the equation can be written as:
T(n) = aT(n/b) + f(n) = 2T(n/2) + O(n) Where, a = 2 (each time, a problem is divided into 2 subproblems) n/b = n/2 (size of each sub problem is half of the input) f(n) = time taken to divide the problem and merging the subproblems T(n/2) = O(n log n) (To understand this, please refer to the master theorem.) Now, T(n) = 2T(n log n) + O(n) ≈ O(n log n)
The divide and conquer approach divides a problem into smaller subproblems, these subproblems are further solved recursively. The result of each subproblem is not stored for future reference, whereas, in a dynamic approach, the result of each subproblem is stored for future reference.
Use the divide and conquer approach when the same subproblem is not solved multiple times. Use the dynamic approach when the result of a subproblem is to be used multiple times in the future.
Let us understand this with an example. Suppose we are trying to find the Fibonacci series. Then,
Divide and Conquer approach:
fib(n) If n < 2, return 1 Else , return f(n - 1) + f(n -2)
mem = [ ] fib(n) If n in mem: return mem[n] Else, If n < 2, f = 1 Else , return f(n - 1) + f(n -2) mem[n] = f return f
In dynamic approach, mem stores the result of each subproblem.
), whereas using the divide and conquer approach (ie. Strassen's matrix multiplication) is
). Other problems such as the Tower of Hanoi are also simplified by this approach.