Divide and conquer is a recursive problem-solving approach in data structure and algorithms that divide the problem into smaller subproblems, recursively solve each subproblem, and combine the solutions to the subproblems to get the solution of the original problem. So, there are three parts of problem-solving using divide and conquer:
Divide: We divide the problem into one or more than one smaller sub-problems, where sub-problems are the smaller versions of the same problem for less input size.
Conquer: We solve each sub-problem recursively i.e. calling the same function for a smaller input size. Here recursion will automatically do the work for us.
Combine: We combine the solutions to subproblems to build the solution to the original problem.
We need to take care of several critical steps during the implementation of the divide and conquer approach:
Based on comparison with the middle value, we search recursively on either the left or right half until we find the key or reach the base case.
Base case: When the left end crosses the right end, the subarray size shrinks to zero, i.e., if (l > r), return -1.
Divide: Calculate the middle index i.e., mid = l + (r — l)/2
Combine: No need for this step. Think!
Input array will look like this after the partition process similar to quicksort: X[ l…pos — 1] < pivot < X[pos + 1…r ]. The pivot element is present at index pos, and pos — l elements are smaller than the pivot. So pivot element is (pos — l + 1)th smallest element in the array.
We recur for either the left or right side based on comparing k and pivot position. In other words, we solve the problem using only one sub-problem.
We divide the input array of size n into two equal sub-array of size n/2, recursively sort both subarrays and merge the sorted halves to sort the complete array.
We divide the input array into two sub-arrays using the partition process and sort each sub-problems 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 X[l…mid] 2) Entirely in the right sub-array X[mid+1…r] 3) Subarray crossing the mid-point. This includes some rightmost elements of the left subarray and some leftmost elements of the right subarray.
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 two popular ways to solve such recurrence relations: The recursion tree method and the Master method. You can explore this blog to understand how to analyze divide and conquer algorithms: Analysis of recursion in programming.
We implement a divide and conquer algorithm using recursion, which uses a call stack. So space complexity depends on the size of the recursion call stack, which is equal to the depth of the recursion tree.
One must ensure that the memory allocated for the recursion stack is sufficient. Otherwise, the execution may fail because of stack overflow. In other words, time-efficient divide and conquer algorithms often have relatively small recursion depth.
Since the sub-problems are independent, they can be computed in parallel. It is a natural parallel algorithmic approach, leading to a large amount of parallelism. Even if we only divide our problem into two sub-problems, each sub-problem will generate two more smaller sub-problems, and so on.
Due to this property, divide-and-conquer algorithms can be used for execution in multi-processor or shared-memory systems. Data communication between processors does not need to be planned in advance because distinct sub-problems can be executed on different processors.
It can also 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 may lead to many recursive calls and huge recursive stacks. This may lead to an increase in time and space complexity. On the other hand, we can choose the base case smartly to terminate the recursion after fewer steps. This can improve efficiency by a significant factor.
For example, a quicksort algorithm could stop when 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 sufficiently small. The idea is simple: a base case larger than two can reduce many recursive calls and recursion stack size.
The following recursion tree diagram is an example of finding max and min for input size 16 elements. We can observe that the total number of recursive calls will reduce if we terminate at a larger base case.
Sometimes, we can also optimize the divide and conquer solution by reducing the total number of sub-problems count. The idea is simple: it will reduce the count of recursive calls by a significant margin. The best example of this is calculating the power function, Karatsuba algorithm, and Strassen matrix multiplication. We will add more insights in detail related to this idea.
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 weekly content on data structure and algorithms, machine learning, system design and oops.