21-05-2013, 11:54 AM
Divide and Conquer Strategy
Divide and Conquer.pdf (Size: 136.07 KB / Downloads: 26)
This strategy can be applied when the problem can be divided into sub-problems whose
solutions can be combined to construct the solution of the problem. The steps are :
1) Divide : Obtain solution directly if possible, otherwise divide the problem into subproblems.
2) Conquer : Solve the sub-problems recursively.
3) Combine : Build the required solution from the solutions of the sub-problems
Recursion continues till a sub-problem becomes small enough for direct solution. The
recursive algorithm can be implemented non-recursively for greater efficiency.
When the sub-problems are of equal size a recurrence equation can be set up for the time
spent on computation. A theorem called the Master theorem can be used to solve such
equations and thereby we can obtain asymptotic bounds for the problem.