Divide and Conquer Algorithm
Divide and Conquer Algorithm is an efficient approach to solve large problems by following 3 easy steps:
1. Breaking a problem into subproblems
2. Finding the solution to each subproblem
3. Combining the solutions to get the result
So basically, if we consider a problem of size=n, we will follow 3 steps to solve it as depicted in the flow chart-:
- DIVIDE- Firstly, we will divide the problem into subproblems each of size n/2.
- CONQUER- Then, we will find the solution to each of the subproblems.
- COMBINE- Finally, we will combine the subproblem solutions to get the original solution.
Thus, the logic behind this algorithm is-:
If the value is small, we return the solution, else we follow the 3 steps- Divide, Conquer, Combine and then return the final solution.
-> Time Complexity
Each of the 3 step has its own time complexity:
· Case I:
Size (n) is small
Then, Time complexity= O(1)
· Case II:
Size (n) isn’t small
Let the time complexity to solve the original problem be T(n)
So, the time complexity to solve each of the subproblem becomes T(n/2)
and the time taken to divide/combine the solutions of the subproblems becomes f(n)
Therefore, the total time complexity becomes:
T(n)= f1(n) + T(n/2) + T(n/2) + f2(n)
T(n)= f1(n) + 2T(n/2) + f2(n)
-> Algorithms based on Divide and Conquer Approach:
1. Merge Sort- A sorting algorithm wherein an array is divided into two halves, each of the halves is sorted recursively and finally merged together.
2. Binary Search- A searching algorithm in which the algorithm compares the input element x with the value of the middle element in the array in every step. If the values match, then it returns the index of the middle element. Otherwise, if x is less than the middle element, then the algorithm recurs for left side of the middle element, else recurs for the right side of the middle element.
3. Quick Sort- A sorting algorithm in which the algorithm first picks a pivot element, then rearrange the array elements in such a way that all elements smaller than the picked pivot element move to left side of pivot, and all greater elements move to right side. Finally, the algorithm recursively sorts the subarrays on left and right of pivot element.
4. Closest Pair Problem- The objective of this problem is to find the closest pair of points in a set of points in x-y plane. The problem can be solved in O(n²) time by calculating distances of every pair of points and comparing the distances to find the minimum. However, the Divide and Conquer algorithm solves the problem in O(nlogn) time.
5. Strassen’s Algorithm- An efficient algorithm to multiply two matrices in O(n².8974) time.
This isn’t all, there are some more algorithms following the Divide and Conquer Approach.
It should noted here that,
Divide and Conquer approach helps to reduce Time Complexity to a large extent.
For Eg- The Time complexity for Linear Search is O(n) which is much more than that of Binary Search which follows the Divide and Conquer approach and has a time complexity of O(log n). Similarly, the time complexity for Bubble Sort is O(n²) whereas that of Quick Sort, which is an application of Divide and Conquer is O(nlogn).
->Advantages of Divide and Conquer:
1. Helps in solving difficult problems
· Dividing a problem into sub problems makes it easy to solve and get to the solution.
For Eg- The famous Mathematics Puzzle “Tower of Hanoi” wherein we have three rods and n disks, and the aim is to move the entire stack to another rod following some rules.
· This approach improves the asymptotic cost of the solution.
->Disadvantages of Divide and Conquer:
1. Recursion is slow
· The step which involves finding solution to the subproblems through recursion takes place at a slower pace.
2. Becomes complicated with larger values of n (size)
· It is easy to solve a problem with greater size by adding a loop instead of dividing it into subproblems and then combining them.
Despite these disadvantages, Divide and Conquer Algorithm is one of the most preferred algorithm when it comes to solving problems.
-> Divide and Conquer or Dynamic Programming ?
- Students do get confused in deciding where to use Divide and Conquer and where to use Dynamic Programming as both these approaches divide a problem into sub problems.
- To make this clear, one should use Divide and Conquer in the situation where we are not evaluating the same subproblems multiple times like in the case of Binary Search.
- On the other hand, we should you Dynamic Programming in cases where we need to evaluate the same subproblems multiple times. For Eg- A program in which we need to calculate the nth Fibonacci number.
-> Let’s have a look at an example to understand D&C better:
We would be solving a problem based on Merge Sort using Divide and Conquer Approach.
Our task is to sort the array given in the image using Divide and Conquer.
We would follow the following steps to sort this array-:
Step 1- Firstly, we would divide the problem into two halves i.e., into subproblems.
Step 2- Next, we would focus on the left half first and then the right part. So, we would further divide the left half into two parts.
Step 3- Now, we would divide the leftmost part until the size becomes 1.
Step 4- Once the size becomes 1, we would combine the values of the leftmost part of the left side in ascending order (No. 4–6).
Step 5- Similarly, we would solve the right part of the left half and then combine both the halves to get the solution to the left side.(No. 7–9)
Step 6- We would follow similar approach for the right side as well (No. 10–17)
Step 7- Finally, we would combine the subproblems i.e., the left and the right halves to get the final solution (No. 18)
*The numbers 1 to 18 depict the order in which the problem is solved.
Thus, this is how we sort elements through Merge Sort using Divide and Conquer Approach.
Time Complexity of Merge Sort= θ(nLogn) for all the 3 cases ( Best, Average, Worst)
Divide and Conquer follow 3 steps-:
1. Divide- Breaking a problem into subproblems.
2. Conquer- Solving the subproblems recursively.
3. Combine- Combining the solutions to the subproblems.
It is one of the most efficient algorithm and makes the task of solving problems quite easy with reduce time complexity.
For more, check out this video https://youtu.be/dnGhh0RoJ6g wherein I have tried explaining the concept in the best way I could.