Divide and Conquer
Divide and Conquer is an amazing technique for acing technical interviews and optimizing algorithms. Many algorithms, such as Binary Search, Merge Sort, use it.
It is a type of algorithm which is used to break down a problem into sub problems which can be solved easily. When a problem is broken in such a way, the time complexity often decreases exponentially from O(n) to O(n log n).
This algorithm can be understood in three parts. Firstly, we divide the problem into various sub problems. Secondly, we conquer these sub problems by solving them recursively. Finally, we combine solution of all these sub problems to get our final solution.
Suppose we have 8 numbers [1,2,3,4,5,6,7,8]. We have to add these numbers. We will arrange these numbers in such a way that these can be added by adding 2 numbers at a time and then adding further to get the total sum. So, by this method we have converted these numbers into sub problems and then combined these sub problems to get our final solution. This is how divide and conquer works.
We can also use divide and conquer if we have to find a unique value in a group of duplicates. Let’s suppose we have 12 balls. 11 of them have equal weights and one is heavy. We have to find the heavier element.
Now, these are 11 identical balls numbered 1 and one different ball numbered 2. We have to find the location of ball numbered 2. So, one method can be that we can iterate through entire list which will have complexity of O(n) in worst case scenario. So, we can optimize this problem using divide and conquer.
So, using divide and conquer, we will divide this array into sub arrays of equal length. Now we will recursively compare these arrays to find the heavier element. The gap in number of calculations between the two methods increases as we increase the size of the array. The brute force version will always have O(n -1) while the divide and conquer method will have complexity of O(n log n).
A divide and conquer algorithm tries to break a problem down into as many sub problems so that it becomes easier to solve. It does this with recursion.
Recursion is when a function calls itself. As we know that divide and conquer takes place in 3 steps, divide, conquer and combine. Now we’ll look at an example of finding the factorial of a number.
From the code above, the divide part is also the recursion part. We divide the problem at return n * recur_factorial(n-1). The recur_factorial(n-1) is the part where we divide the problem.
The conquer part is also the recursion part, but also the if statement. We can solve the problem directly by returning n if the problem is short but if there are bigger numbers we will need to follow this approach.
The combine part is the multiplication symbol. Eventually, we will return the factorial of the number but if there is no multiplication symbol between return n and recur_factorial(n-1) then no combination will take place and we will not get the desired result.
These were some basic examples of divide and conquer algorithm. Now, we will look at how divide and conquer works in some famous algorithms such as merge sort and binary search.
Merge sort is a sorting algorithm. In this algorithm, we are given an array of elements which we are required to sort in ascending or descending order according to the given condition.
Finding all the permutations of the sequence and seeing if it's sorted is the most naive way possible. Since it will take N! permutations of the array and N iterations to verify whether they are sorted, the time complexity of this method will be O(N*N!). So, this approach can be discarded immediately.
We can sort the array in a slightly better way by taking each element into account and putting them in their proper positions. Even then, the time complexity will be O( N² ), which will not work for large arrays. We’ll look at an optimized approach of solving the problem using divide and conquer.
This algorithm works in the following three steps:
- Divide the given array of n numbers into 2 halves
- Sort the 2 halves recursively
- The 2 sorted halves is merged into a single sorted array
In this example, we divide the given array into two halves. Then, we continue dividing this array recursively until we get individual elements. Then, we use these individual elements and combine them step by step to get our final desired result.
Thus, we can see from this example that we have first broken down our problem into sub problems and these sub problems are recursively divided such that we obtain individual elements. Then, these elements are combined step by step again to obtain the final sorted array. Hence, this becomes a classic case of divide and conquer algorithm.
Now, we will see that how we can use this algorithm in binary search.
Binary search is a search algorithm which is used to find the position of a value in a sorted array. Note: Binary search only works in a sorted array. So, to find a given number by traversing the whole array will be a naive approach. That’s why we use divide and conquer.
We search a number x in a sorted array by repeatedly dividing the search interval in half. We begin with the middle value of the array which covers the entire interval. If the value of the search key is less than the middle value of the interval, we narrow down the interval to the lower half else we narrow it down to the upper half. We repeatedly do this procedure until we get the value or until interval becomes empty if value is not found.
So, as we discussed, merge sort and binary search are two of the best use cases of divide and conquer algorithm.
Divide and Conquer is a basic algorithmic technique that improves the efficiency and speed of our tasks.
We must look to see if we can apply this technique to make our tasks simpler whenever we find a problem in which we can break down the given problem into simpler sub-problems.
This is one of the simplest ways to optimize our algorithms and make our programs fast.