1. What is Divide and Conquer?
Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem. A typical Divide and Conquer algorithm solves a problem using following three steps.
1. Divide: Break the problem into sub-problems of same type.
2. Conquer: Recursively solve these sub-problems.
3. Combine: Combine the solution sub-problems.
For Example: Assuming that each divide step creates two sub-problems
If we can divide the problem into more than two, it looks like this:
2. Standard Algorithms based on Divide and Conquer
The following algorithms are based on divide-and-conquer algorithm design paradigm −
- Merge Sort
- Quick Sort
- Binary Search
- Strassen's Matrix Multiplication
- Closest pair (points)
- Cooley–Tukey Fast Fourier Transform (FFT) algorithm
- Karatsuba algorithm for fast multiplication
3. Advantages of Divide and Conquer
- The most recognizable benefit of the divide and conquer paradigm is that it allows us to solve difficult problem, such as the Tower of Hanoi, which is a mathematical game or puzzle. Being given a difficult problem can often be discouraging if there is no idea how to go about solving it. However, with the divide and conquer method, it reduces the degree of difficulty since it divides the problem into sub problems that are easily solvable, and usually runs faster than other algorithms would.
- It also uses memory caches effectively. When the sub problems become simple enough, they can be solved within a cache, without having to access the slower main memory.
4. Disadvantages of Divide and Conquer
- One of the most common issues with this sort of algorithm is the fact that the recursion is slow, which in some cases outweighs any advantages of this divide and conquer process.
- Sometimes it can become more complicated than a basic iterative approach, especially in cases with a large n.
In other words, if someone wanted to add a large amount of numbers together, if they just create a simple loop to add them together, it would turn out to be a much simpler approach than it would be to divide the numbers up into two groups, add these groups recursively, and then add the sums of the two groups together.
