Tuesday, January 24th, 2017
The very general idea of Divide and Conquer proof is to partition a problem into roughly equal subproblems and solve them and then recombine to prove the desired bound on the function based on the already defined subproblems.
If you can’t solve the problem, divide it into parts, and solve one part at a time. This strategy is one that is built on the premise that “Rome wasn’t built in a day”.
The Divide and Conquer strategy has its roots from the colonial-wars tactics employed by army generals to defeat their opposing armies. To apply the strategy, we divide an instance of a problem into two (or more) smaller-sized instances whose solutions will be combined to obtain the solution to the original problem.
Divide and Conquer works best when all subproblems are independent.
The basic idea of this solving problem technique is: If the problem is easy, solve it directly; If the problem cannot be solved as is, decompose it into smaller parts; solve the smaller part.
Summing-up: An elephant is eaten one bite at a time. The walk of thousand miles starts with the first step. The only way that we can deal with the complexities of life is the same method that has been used for the last 5,000 years – Divide and Conquer.
These notes have been taken from: