Divide and Conquer Paradigm
Divide and Conquer Paradigm
In previous post, we looked at Merge Sort, an implementation of Divide and Conquer Paradigm of algorithm design. Divide and Conquer paradigm, as the name implies divides the harder problems into sub-problems which are in comparison easier to solve recursively breaking down the harder problem into easier problems and then combining the solution of the simpler problem's to get the result.
This approach thus simplifies the process of solving the given problem.
There are various reasons to use divide and conquer approach such as:
- Making Problems simpler
- Increase Algorithmic Efficiency
- Increase Parallelism
- Better understanding of roots/foundation of the problem
1. Making Problems Simpler:
By Making Problems simpler, it means that we generally try to break down the given problem which are more easier to solve thus making it more easy to solve the problem at hand.
One practical (human related, not to be confused with computing) application is, Try the addition of 7283 + 8920 in your mind. Now after that try adding : 7000+8000+200+900+80+20+3.
You will most likely find the second one easier, even though there are many subproblems at hand, but those subproblems looks kind of much simpler as in trying to solve the complex one.
2. Increase Algorithmic Efficiency:
By Increase Algorithmic Efficiency, it means that generally when Divide and conquer approach is implemented , in computing sense, The Asymptotic complexity of the algorithm usually decrease. We can see the same in previous sorting algorithm we have studied: Insertion Sort vs Merge Sort.
Insertion sort being an O(n^2) while Merge Sort being O(nLogn) .
3. Increase Parallelism:
By Increase Parallelism, it means that if we divide the given problem into subproblems, we have k subproblems at hand and those k subproblems can then be processed by parallel processor, where each processor is processing one problem at a time thus increasing parallelism, and promoting it rather than central processing concept.
4. Better Understanding of roots/foundation of the problem:
Well, It simply means that if you know the problem at hand completely, then you can divide it into simpler problems, which are much more basic and forms the foundation of the given problem. It displays the understanding of the complex problems, and their nature.
-Written By, Sarvesh Bhatnagar
