next up previous contents index CD CD Algorithms
Next: Fast Exponentiation Up: Breaking Problems Down Previous: War Story: Text Compression

Divide and Conquer


Divide and conquer was a successful military strategy long before it became an algorithm design paradigm. Generals observed that it was easier to defeat one army of 50,000 men, followed by another army of 50,000 men than it was to beat a single 100,000 man army. Thus the wise general would attack so as to divide the enemy army into two forces and then mop up one after the other.  

To use divide and conquer as an algorithm design technique, we must divide the problem into two smaller subproblems, solve each of them recursively, and then meld the two partial solutions into one solution to the full problem. Whenever the merging takes less time than solving the two subproblems, we get an efficient algorithm. Mergesort, discussed in Section gif, is the classic example of a divide-and-conquer algorithm. It takes only linear time to merge two sorted lists of n/2 elements each of which was obtained in tex2html_wrap_inline24820 time.  

Divide and conquer is a design technique with many important algorithms to its credit, including mergesort, the fast Fourier transform, and Strassen's matrix multiplication algorithm. However, with the exception of binary search, I find it to be a difficult technique to apply in practice. Therefore, the examples below will illustrate binary search and its variants, which yield simple algorithms to solve a surprisingly wide range of problems.

Mon Jun 2 23:33:50 EDT 1997