Divide and Conquer Algorithm

The divide and conquer approach as the name suggests divides the given problem in parts and then each problem is solved independently. When we keep dividing the problem into smaller parts a moment comes when the problem cannot be divided further into smaller part, then those smaller parts are solved and the solution of all those smaller parts or sub-parts is finally merged to obtain the solution of the original problem.

Divide and Conquer Algorithm

This Algorithm is very useful and has very interesting applications, advantages, disadvantages. We will look at them closely at each one of them in this blog, which will make you understand why this algorithm is very useful in this world.

So what are you waiting for ? Let’s get Started!

Divide and Conquer Algorithm contains the following steps:

1. Divide: This involves dividing the problem into smaller sub problem.
2. Conquer: Solving the smaller sub-problems recursively.
3. Combine: Combine the solutions of the sub-problems that are part of the recursive process to solve the actual problem.

When&Where to use Divide and Conquer Algorithm:

This algorithm will be useful if we have a problem that closely relates to the divide and conquer algorithm. We can use this algorithm where the problem can be divided into sub-problems but make sure that the same sub problem should not be solved several times. If the same sub-problem is solved several time then you should understand, that this problem will be solved by dynamic approach rather than Divide and Conquer Algorithm.

Advantages of Divide and Conquer:

1. This algorithm makes the given problem easier as it divides the given problem into sub-problems which makes it easier to solve and then solving each of them individually and combining all the solution of all sub-problem into one to solve the original problem.
2. The algorithm increases the efficiency of other algorithms such as quick sort, merge sort etc. These algorithms are the application of Divide and Conquer Algorithm.
3. This algorithm is supported by most of the processors especially with shared memory system where data communication between processors does not need to be pre-programmed.
4. This algorithm uses memory caches in an efficient manner.

Disadvantages of Divide and Conquer:

1. The main problem which arises with this algorithm is the recursion is slow that increases the time complexity.
2. Another problem which this algorithm is that sometimes it becomes complicated while solving the problem through this approach and the basic iterative approach seems more easier.
3. While solving the problems through this approach sometimes there are same sub-problems. So its best to save the solution to the repeated sub problem.
4. While using this algorithms, make sure there is enough memory allocated to the return stack; otherwise, processing may fail due to stack overflow.

Divide and Conquer Applications:

1. Binary Search: This is a fast search algorithm which works on the principle of the Divide and Conquer Algorithm. For this algorithm to work properly, the data should be in the sorted form. This algorithm looks for a particular item by comparing the middle most item of the collection. If a match occurs, then the index of item is returned. If the middle item is greater than the item, then the item is searched in the sub-array to the left of the middle item. Otherwise, the item is searched for in the sub-array to the right of the middle item. This process continues on the sub-array as well until the size of the sub array reduces to zero.
2. Merge Sort: This sorting technique also works on the principle of Divide and Conquer Algorithm. This algorithm first divides the array into equal halves and then combines them in a sorted manner.
3. Quick Sort: This sorting technique also works on the same principle. This algorithm picks a pivot element, rearranges 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 sub arrays on left and right of pivot element.
4. Strassen’s Matrix multiplication: This technique also work on the same principle. This technique is an efficient algorithm to multiply two matrices.

Time Complexity

The complexity of the divide and conquer algorithm is calculated using the master theorem which is as follow.

T(n) = aT(n/b) + f(n),
where,
n = size of input
a = number of subproblems in the recursion
n/b = size of each subproblem. All subproblems are assumed to have the same size.
f(n) = cost of the work done outside the recursive call, which includes the cost of dividing the problem and cost of merging the solutions

Now lets take an example by finding the time complexity of a recursive problem

T(n) = aT(n/b) + f(n)
     = 2T(n/2) + O(n)
Where, 
a = 2 (each time, a problem is divided into 2 subproblems)
n/b = n/2 (size of each sub problem is half of the input)
f(n) = time taken to divide the problem and merging the subproblems
T(n/2) = O(n log n) (To understand this, please refer to the master theorem.)

Now, T(n) = 2T(n log n) + O(n)
          ≈ O(n log n)

Also this algorithm allows us to reduce the time complexity by a large extent.

For example, Bubble Sort uses a complexity of O(n ^ 2) , whereas quick sort (an application Of Divide And Conquer) reduces the time complexity to O(nlog(n)). Linear Search has time complexity O(n), whereas Binary Search (an application Of Divide And Conquer) reduces time complexity to O(log(n)).

Summary

The first task you have to identify that the given problem can be solved by the Divide and Conquer algorithm or not. Once you get that the problem can be solved by the D&C Algorithm then your task becomes easier because now you have to just follow three steps: Dividing the given problem into sub-problems using recursive calls, Solving the sub-problems and then combining them all together to find the answer to the original problem. This algorithm also reduces the time complexity to large extinct.

That’s all for this blog . I hope you all understood the topic. If you have any doubt(s) regarding this, you can leave a comment or contact me on LinkedIn.