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!
You are given an array X consisting of n elements, write a program to find majority element in an array i..e return the number which appears more than n/2 times. You may assume that the array is non-empty and the majority element always exists in the array. A majority element is an element that appears more than n/2 times, so there is at most one such element.
In recursive DFS traversals of a binary tree, we have three basic elements to traverse— root, left subtree, and right subtree. The traversal order depends on the order in which we process the root node. Here recursive code is simple and easy to visualize — only one function parameter and 3–4 lines of code. So critical question would be — How can we convert it into iterative code using stack? To simulate the recursive traversal into an iterative traversal, we need to understand the flow of recursive calls.
Hashing is a technique to map (key, value) pairs into the hash table using a hash function. It uses an array of size proportional to the number of keys and calculates an array index from the key using a hash function. Explore this blog to learn how hash tables work in programming?
Given an array A of integers, find out the maximum difference between any two elements such that the larger element appears after the smaller element. In other words, we need to find max(A[j] - A[i]), where A[j] > A[i] and j > i. This is an excellent problem to learn problem-solving using divide and conquer, transform and conquer and a single loop.
There can be four reasons to learn data structures and algorithms: 1) An algorithm is a technology in itself! 2) It is at the core of library functions and APIs 3) It is important for cracking the coding interview 4) Algorithms are beautiful! This blog will help you develop a long-term motivation for learning DSA.
Subscribe to get free weekly content on data structure and algorithms, machine learning, system design, oops design and mathematics.