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. Conquer: Solving the smaller sub-problems recursively.
  2. 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:

Advantages of Divide and Conquer:

  1. 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.
  2. 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.
  3. This algorithm uses memory caches in an efficient manner.

Disadvantages of Divide and Conquer:

  1. 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.
  2. 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.
  3. 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. 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.
  2. 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.
  3. Strassen’s Matrix multiplication: This technique also work on the same principle. This technique is an efficient algorithm to multiply two matrices.

Time Complexity

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

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.

Developer|Writer

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store