Introduction:
There are a number of algorithms which help us to reduce time complexity or space complexity of programs and divide and conquer is one of them. Divide and conquer algorithm has been here for ages and can be traced back to as far as the 200 BC in Babylonia. Historical examples of the use of the algorithm include Cooley–Tukey fast Fourier transform (FFT), binary search, merge sort and the Euclidean algorithm to compute the greatest common divisor of two numbers. As the name suggests, divide and conquer algorithm can be understood in three simple steps, that is:
1. Divide
2. Conquer
3. Merge.
In step one, divide, we create sub problems from the main problem whereas in step two, each of these subproblems are solved. In the last step, the solutions of these subproblems are combined to get the final result. Therefore, divide and conquer algorithm causes the problem to be subdivided until further division is not possible. If you know the base case of a given problem (or the solution of the atomic subproblem), divide and conquer algorithm may prove useful. This algorithm is great for optimization purposes. It can also help us solve problems which would otherwise be nearly impossible like the Tower of Hanoi. This algorithm is particularly useful for sorting, searching and matrix multiplication. Binary search, Quick sort, Merge sort, Closest pair of points, Strassen’s algorithm, Cooley–Tukey Fast Fourier Transform (FFT) algorithm and Karatsuba algorithm for fast multiplication are notable examples of the divide and conquer algorithm.
Working of the algorithm with the help of an example:
This algorithm’s classic implementation is the binary search where at each step the sorted array is divided into half until the wanted element is found or it is discovered that the wanted element is not in the array. In this case, we can see how the algorithm divides the array until one (or zero) element is left. This causes the number of comparisons to be drastically reduced. Without the divide and conquer algorithm at our rescue, we would most likely compare each and every element of the array to the wanted element, thereby wasting time. The time complexity of binary search is O(nlogn) which is an improvement from O(n) of linear search. In binary search, the reason for this radical reduction in time complexity can be attributed to the decrease in search space by half at every iteration.
This example shall help drive the point further. Note that the parts of the array that are no longer required are not shown for the sake of simplicity.
Step 1: We have an integer array of size 9 that is sorted in the ascending order and the wanted element is 15.
Step 2: The middle element is 17 which is not equal to 15. Since 15 is smaller than 17, the wanted element will most probably be in the left part of the array so we divide it into half.
Step 3: After the division of the array, our focus is on four elements and the middle element now is 12. In the case of an array with even elements like this one, either 12 or 14 could be considered as the middle element but we went for the element 12. Yet again, 12 and 15 are not equal and since 15 is greater than 12, we will divide this ‘sub-array’ into half and focus exclusively on the right side.
Step 4: 14 is the middle element of this sub array and since 14 is lesser than 15 we will divide it into half.
Step 5: The wanted element 15 is found.
Advantages of the algorithm:
The advantages of the divide and conquer algorithm are many. Some of them include increased ease in solving difficult problems since all that is needed is to divide the problem till it’s simplest form is reached. The Tower of Hanoi is a good example of this as here the tower is reduced from a height n to a height n-1 at each step. If the base case can be solved in constant time, the asymptotic time complexity is O(n logpn) where n is the size of the main problem, p is the bounded number of subproblems each of approximately size n/p. The It is a great idea to use divide and conquer if you are using multiprocessor systems since parallelism is one of the main features of this algorithm. It also makes efficient use of memory caches. This is because each subproblem is fairly simple and can be solved within the cache.
Disadvantages of the algorithm:
Like any other algorithm, divide and conquer has it’s own set of disadvantages. For example, this algorithm inherently requires recursion. To keep dividing a subproblem until an atomic problem is reached requires recursion and so does combining multiple subproblems. If divide and conquer algorithms are implemented by a non-recursive program that stores the partial sub-problems in some explicit data structure, such as a stack, queue, or priority queue. This approach allows more freedom in the choice of the sub-problem that is to be solved next. In case, recursion is used it must be ensured that there is enough memory space so that there is no stack overflow issue caused while dividing subproblems. Stack overflow may be difficult to avoid when using recursive procedures since many compilers assume that the recursion stack is a contiguous area of memory. Another major difficulty that may be caused by the divide and conquer algorithm is what should be chosen as the base case or the atomic problem. This is the singular most important question for any problem utilizing divide and conquer algorithm. While in some cases ,like the binary search problem it is quite obvious as to what is the base case, not all problems guarantee this simplicity and you will have to rack your brains to find the atomic subproblem. In many situations, a similar subproblem may come up over and over again. This may cause an increase in time taken because the algorithm will have to solve the same problem multiple times. In order to resolve this, memorization is useful as the solutions of previous subproblems are noted and can be looked up to ensure that there is no repetition.
Conclusion:
I hope this blog helped you understand divide and conquer algorithm and will be useful to you while using this algorithm for solving a problem more efficiently.
Author: Riya Jha
2nd year ,B.Tech CSE student at Bennett University
