In data structures and algorithms, Divide and Conquer is a recursive problem-solving approach that divides the problem into smaller subproblems, recursively solves each subproblem, and combines the subproblem's solutions to get the solution of the original problem. So, there are four steps in the divide and conquer algorithm:
Note: Before learning this strategy, we recommend exploring the concept of recursion.
Based on a comparison with the middle value, we recursively search for the target value in either the left or right half. This process will continue until we find the target value or reach the base case. In other words, we solve the searching problem of size n using one sub-problem of size of n/2.
Divide: Calculate the mid index, i.e., mid = l + (r - l)/2.
Combine: There is no need for this step. Think!
Base case: When left end crosses the right end, the subarray size will be zero i.e. if (l > r), return -1.
Divide: We divide the array into two subarray using the partition algorithm (partition process similar to quick sort). After the partition, partition algorithm will return the index of the pivot. So array X[l, r] will look like this: X[l, pos - 1] < pivot < X[pos + 1, r]. Note: Here pos is the index of pivot after the partition.
Conquer: If pivot is present at index pos, then (pos - l) elements are smaller than the pivot. In other words, pivot is the (pos - l + 1)th smallest element in the array.
Combine: One of the sub-problems in the conquer step will return the value of the kth smallest. So there is no need to combine the sub-problems. Note: Assume that l <= k <= r.
Base case: If l == r, return X[l]. In other words, the case of a single-element is the base case.
We divide the array of size n into two equal sub-arrays of size n/2, recursively sort both sub-arrays and merge the sorted halves to sort the complete array.
We divide the array into two sub-arrays using the partition algorithm and sort each sub-array recursively to get the final sorted array.
We divide the array into two equal subarrays: X[l, mid] and X [mid + 1, r]. Then the sub-array X[i, j] with maximum sum must lie in one of these places: 1) Entirely in the left sub-array 2) Entirely in the right sub-array 3) Subarray crossing the mid-point.
There are a few cases where we use more than two subproblems to get the solution to the final problem. We will add detailed insights about this idea later.
We use recurrence relation to define the time complexity of divide and conquer algorithms. If T(n) is the time complexity for input size n, then T(n) = Time complexity of the divide part + Time complexity of the conquer part + Time complexity of the combine part.
The above approach provides a way to define the recurrence relation of the divide and conquer algorithm. Now we solve the recurrence relation and calculate the overall time complexity in terms of Big-O notation.
There are three popular ways to solve such recurrence relations: Recursion tree method, Master method and substitution method. You can explore this blog to understand the detailed analysis of divide and conquer algorithms: Analysis of recursion in programming.
We implement a divide and conquer algorithm using recursion, which involves a call stack. So the space complexity depends on the size of the recursion call stack, which is equal to the depth of the recursion tree. The overall space complexity of the divide and conquer algorithm = Size of recursion call stack + Extra space used inside the code.
It is essential to ensure that the memory allocated for the recursion stack is sufficient. Otherwise, the execution may fail due to stack overflow. In other words, time-efficient divide and conquer algorithms usually have a relatively small recursion depth.
Since the sub-problems are independent, we can calculate them in parallel. In other words, divide and conquer is a natural parallel algorithmic approach that leads to a large amount of parallelism. Even if we only divide the problem into two sub-problems, each sub-problem will generate two more smaller sub-problems, and so on.
Because of this property, we can use divide-and-conquer algorithms for execution in multi-processor or shared-memory systems. There is no need to plan the data communication between processors in advance because we can execute distinct sub-problems on different processors.
Additionally, divide-and-conquer algorithms can make efficient use of memory caches. The idea is simple: Once a sub-problem is small enough, it can be solved within the cache without accessing the main memory.
Sometimes, recursion with small base cases can lead to many recursive calls and huge recursive stacks. This may increase time and space complexity. On the other hand, we can choose the base case wisely to terminate recursion after fewer steps. This will reduce the number of recursive calls significantly and improve the performance.
For example, a quicksort algorithm could stop when there is a single input or input is empty. To improve efficiency, we can switch to a simple loop-based insertion sort algorithm once the number of items to be sorted is small enough. The idea is simple: Base case larger than two can reduce many recursive calls and the recursion stack size.
The following recursion tree diagram is an example of finding the maximum and minimum for an input size of 16 elements. We can observe that the total number of recursive calls will decrease if we terminate at a larger base case.
Sometimes, we can optimize the divide and conquer solution by reducing the total number of sub-problems. The idea is simple: it reduces the number of recursive calls significantly. The best examples of this are calculating the power function, Karatsuba algorithm, and Strassen matrix multiplication. We will provide more insights about this idea later in a separate blog.
We will keep updating this blog to add more insights. Please share your feedback or insights to improve this further. Enjoy learning, Enjoy algorithms!
Subscribe to get well designed content on data structure and algorithms, machine learning, system design, object orientd programming and math.
©2023 Code Algorithms Pvt. Ltd.
All rights reserved.