Divide and Conquer Algorithm

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.

Steps of divide and conquer algorithms

How to implement Divide and conquer algorithms?

We need to take care of several critical steps during the implementation of the divide and conquer approach:

There could be several sub-problems to a problem. So we need to choose the correct sub-problems involved in the solution. In most situations, we divide the problems into two equal parts.
We solve each sub-problems recursively. So we need to carefully decide the input parameters for the recursive call of each sub-problem.
The correct base case is essential for the correctness of the divide and conquers solution. We need to identify the smallest or trivial version of the sub-problem for which we already know the solution.
To implement the conquer stage, we need to identify the correct operation to combine the solutions of sub-problems to get the final solution.

Divide and conquer using one subproblem: Decrease and conquer

Binary search algorithm

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

Conquer

If (X[mid] == key): Return the value mid.
If (X[mid] > key): Recursively search the key in the left half.
If (X[mid] < key): Recursively search the key in the right half.

Combine: No need for this step. Think!

Quick-select algorithm of finding kth smallest

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.

If (pos — l + 1 == k): return X[pos].
If (pos — l + 1 > k): kth smallest is present on the left subarray.
If (pos — l + 1 < k): kth smallest is present on the right subarray.

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.

Divide and conquer using two sub-problems

Merge sort algorithm

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.

Base case: When l == r during the recursive calls, the sub-array has one element left, which is trivially sorted.
Divide: Calculating the middle index i.e., mid = l + (r — l)/2
Conquer: Recursively Sort both the smaller halves.
Combine: Merge both the sorted halves to sort the whole array.

Quicksort algorithm

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.

Base case: When l ≥ r during the recursive calls, the sub-array would be either empty or have one value left.
Divide the problem into two smaller sub-problems by partitioning the array X[l…r] into smaller subarrays around the pivot. The partition process returns the pivotIndex i.e. index of the pivot in the sorted array.
Conquer: Recursively sort both subarrays.
Combine: This is a trivial case because our whole array will get sorted after sorting both smaller arrays.

Divide and conquer solution of finding max and min

Divide the array into two equal parts around mid-value.
Conquer: Recursively find the min and max of both left and right parts.
Combine: Compare the max and min of both halves to get the max and min of the whole array.
Base case 1: If subarray size is 1, return the element as both max and min.
Base case 2: If subarray size is 2, compare both elements and return max and min among them.

Divide and conquer solution of finding max subarray sum

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.

Divide: Calculate the middle index i.e., mid = l + (r — l)/2.
Conquer: Recursively find the max sub-array sum of left and right halves.
Combine: Calculate the maximum sub-array that crosses the mid-point and takes the maximum of all three possibilities.
Base case: When l == r, there is only one element in the array, and we can directly return the max subarray sum as X[l] or X[r].

Divide and conquer solution of finding majority element

Divide: Calculate the middle index i.e., mid = l + (r — l)/2.
Conquer: Recursively find the majority element of the left and right halves.
Combine: If the majority elements of the left and right halves are equal, then it must be the overall majority element. Otherwise, one of them must be equal to the overall majority element. To determine this, count the frequency of the leftMajority and rightMajority in the input array and return the value with maximum frequency as the final output.
Base case: This is the case of a single element array i.e. if (l == r), return X[l] or X[r].

Divide and conquer using more than two sub-problem

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.

Time complexity analysis of divide and conquer

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 time complexity of the divide part is O(1) in most of the scenarios because it calculates the middle index. However, there are a few exceptions! For example, the quicksort divide part is a partition process, which requires O(n) operations.
Suppose we divide the problem into k number of different sub-problems and solve each sub-problem recursively. So time complexity of the conquer part = T(Input size of subproblem 1) + T(Input size of subproblem 2)….+ T(Input size of subproblem k).
The time complexity of the combine part depends on the cost of extra operations to combine the solution of smaller sub-problems. It can be O(1), O(n), O(n^2), etc., based on the nature of the operation.

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.

Space complexity analysis of divide and conquer

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.

Parallelism in divide and conquer algorithms

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.

Optimizing divide and conquer algorithms

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.

Comparing the count of recursive calls for different base cases

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.

Critical ideas to think about!

Divide-and-conquer algorithms can also be implemented by a non-recursive algorithm using an explicit stack data structure. We recommend exploring the stack-based implementation of the merge sort and quicksort.
The risk of stack overflow can also be reduced by minimizing the parameters and internal variables of the recursive calls to the sub-problems.
Divide and conquer solve several challenging problems with less time complexity than its brute-force solution. However, to be efficient, one must ensure that the divide and combine steps are efficient.
There is a difference between the recursive solution of divide and conquer and the dynamic programming problems. Understanding this difference is important for mastering the dynamic programming approach. Note: later, we will write a separate blog to highlight this difference in detail.
We can solve several coding problems using the divide and conquer idea of binary search and merge sort.

We will keep updating this blog to add more insights. Please share your feedback or insights to improve this further. Enjoy learning, Enjoy algorithms!