Hi, I’m Jarvis, thank you for reading my blog ! I’m a student pursuing my bachelors in computer science engineering at Bennett University.
In this blog, I’ll be writing about the Divide And Conquer Algorithm . The outline of this blog will be the discussion of the following topics :
- Introduction to the Divide And Conquer Algorithm
- Algorithms under the Divide And Conquer Algorithm techniques.
- Recurrence Relation for the Divide And Conquer Algorithm.
- The Divide And Conquer Algorithm vs Dynamic Programming.
The Divide And Conquer Algorithm
The Divide and conquer algorithm firstly breaks down a problem into smaller subproblems that are similar to the original problem, and then goes on to recursively solve the subproblems, to finally combines the solutions of the subproblems to solve the original problem. Since the divide and conquer algorithm solves subproblems recursively, there is a condition that each of the subproblems must be smaller than the given original problem. Also, it should be noted that there must be a base case for each of the subproblems.
The divide-and-conquer algorithm should be thought of as having three parts of the process :
1. Divide : Divide the given problem into a number of small subproblems. The small subproblems are nothing but smaller instances of the same given original problem.
2. Conquer : Conquer the smaller subproblems by solving them recursively. But if they happen to be small enough to solve the subproblems up as base cases, then continue to do so.
3. Combine : Combine the solutions of the smaller subproblems to get the main solution for the given original problem.
One can easily remember the process or steps involved in a divide and conquer algorithm by the mnemonic DCC as in Divide, Conquer and Combine.
Let’s assume that each divide step creates two subproblems ( even though in some divide and conquer algorithms 1 divide step creates more than two subproblems ), here’s how one divide step looks like :
If we expand out two more recursive steps for each of the subproblems and then some, since divide and conquer creates two subproblems at the least as this type of algorithm makes multiple recursive calls, the original problem will begin to look something like this :
Algorithms under the Divide And Conquer Algorithm techniques
Now, let us take a look at some of the many standard algorithms that follow Divide and Conquer algorithm :
1. Binary Search : Binary search, as the name suggests, is a searching algorithm. In each step of this particular algorithm, the algorithm compares the input element, say M, with the value of the middle element in an array. If the values turn out to match, then the algorithm returns the index of the middle element of the array. Otherwise, meaning if M is less than the middle element of the array, then the algorithm recurs for left side of the middle element. Also, if M is greater than the middle element of the array, then the algorithm recurs to the right side of the middle element.
2. Quicksort : Quicksort is a sorting algorithm. Theis particular algorithm picks up a pivot element, and then rearranges the array elements in such a way that all the elements smaller than the selected pivot element move to the left side of the pivot, and all the greater elements move to the right side of the pivot. Finally, in this way, the algorithm recursively sorts to arrange the subarrays on the left and right of the pivot element.
3. Merge Sort : Merge Sort is also a kind of sorting algorithm. The algorithm, in this case, divides the whole array in two halves and then recursively sorts them. Once it is all arranged, it finally merges the two sorted halves to make the final sorted array.
4. Closest Pair of Points : Closest Pair of Points is a problem where we have to find the closest pair of points in a set of points given in a x-y plane. This type of problem can usually be solved in O(n²) time by calculating the distances of every pair of points in the given space and then comparing the distances to find the minimum distance. But, the Divide and Conquer algorithm can solve this problem in O( nLog n ) time.
5. Strassen’s Algorithm : Strassen’s Algorithm is an efficient algorithm to multiply any two given matrices. Now, usually, the most simple way of multiplying any two given matrices needs 3 nested loops, and the time taken would be O( n³ ). Using the Strassen’s algorithm, any two given matrices can be multiplied in just O( n².8974 ) time.
6. Cooley–Tukey FFT algorithm : It is the most common algorithm for problems involving Fast Fourier Transform ( FFT ). It is a divide and conquer algorithm which works in just O( nlogn ) time.
7. Karatsuba algorithm : Karatsuba algorithm is for fast multiplication. So what this algorithm basically does is multiplication of two n-digit numbers in at most, single-digit multiplications in general (and exactly when n is a power of 2). It is therefore faster than the classical algorithm, which requires n2 single-digit products. That is, if n = 210 = 1024, in particular, the exact counts are 310 = 59, 049 and (210)2 = 1, 048, 576, respectively.
The Divide And Conquer Algorithm
DivideAndConquer(a, i, j)
{
if(small(a, i, j))
{
return(Solution(a, i, j))
}
else
{
m = divide(a, i, j) — — — — — — — — — — // f1(n)
b = DivideAndConquer(a, i, mid) — — —- // T(n/2)
c = DivideAndConquer(a, mid+1, j) — — -// T(n/2)
d = combine(b, c) — — — — — — — — —-// f2(n)
return(d)
}
}
Recurrence Relation for Divide and Conquer algorithm
This is the recurrence relation for the above divide and conquer algorithm.
O(1) if n is small
T(n) = f1(n) + 2{ T(n/2) } + f2(n)
Divide and Conquer ( D & C ) vs Dynamic Programming ( DP )
In both paradigms ( Divide and Conquer and Dynamic Programming ), the given problem is divided into subproblems, then the subproblems are solved, even parallelly, and then the solutions of the subproblems are combined to get the main solution of the original given problem.
But how does one choose one of them for a given problem?
Here is my conclusion, Divide and Conquer should be used when the same subproblems are not evaluated many times. Otherwise Dynamic Programming or Memoization should be used to solve the given problem.
For example, Binary Search is a Divide and Conquer algorithm, we never evaluate the same subproblems again. But, on the other hand, to calculate the nth Fibonacci number, Dynamic Programming should be preferred to solve such a problem.
Thank You for reading :)
Jarvis | E19CSE425 | EB13 | e19cse425@bennett.edu.in
