The Algorithm Design Manual Second Edition

135

4.10

Divide-and-Conquer

One of the most powerful techniques for solving problems is to break them down

into smaller, more easily solved pieces. Smaller problems are less overwhelming, and

they permit us to focus on details that are lost when we are studying the entire

problem. A recursive algorithm starts to become apparent when we can break

the problem into smaller instances of the same type of problem. Effective parallel

processing requires decomposing jobs into at least as many tasks as processors, and

is becoming more important with the advent of cluster computing and multicore

processors.

Two important algorithm design paradigms are based on breaking problems

down into smaller problems. In Chapter

8,

we will see dynamic programming,

which typically removes one element from the problem, solves the smaller problem,

and then uses the solution to this smaller problem to add back the element in the

proper way. Divide-and-conquer instead splits the problem in (say) halves, solves

each half, then stitches the pieces back together to form a full solution.

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

4.5

(page

120

), 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 O(n lg n) 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. Beyond binary search and its many variants, however, I

find it to be a difficult design technique to apply in practice. Our ability to analyze

divide-and-conquer algorithms rests on our strength to solve the asymptotics of

recurrence relations governing the cost of such recursive algorithms.