Source code online books for professionals by professionals

Chapter 6
Divide, Combine, and Conquer
Divide and rule, a sound motto;
Unite and lead, a better one.
— Johann Wolfgang von Goethe, Gedichte
This chapter is the first of three dealing with well-known design strategies. The strategy dealt with in this chapter, 
divide and conquer (or simply D&C), is based on decomposing your problem in a way that improves performance. 
You divide the problem instance, solve subproblems recursively, combine the results, and thereby conquer the 
problem—a pattern that is reflected in the chapter title.
1
Tree-Shaped Problems: All About the Balance
I have mentioned the idea of a subproblem graph before: We view subproblems as nodes and dependencies (or 
reductions) as edges. The simplest structure such a subproblem graph can have is a tree. Each subproblem may 
depend on one or more others, but we’re free to solve these other subproblems independently of each other. (When 
we remove this independence, we end up with the kind of overlap and entanglements dealt with in Chapter 8.) This 
straightforward structure means that as long as we can find the proper reduction, we can implement the recursive 
formulation of our algorithm directly.
You already have all the puzzle pieces needed to understand the idea of divide-and-conquer algorithms. Three 
ideas that I’ve already discussed cover the essentials:
Divide-and-conquer recurrences, in Chapter 3
•
Strong induction, in Chapter 4
•
Recursive traversal, in Chapter 5
•
The recurrences tell you something about the performance involved, the induction gives you a tool for 
understanding how the algorithms work, and the recursive traversal (DFS in trees) is a raw skeleton for the algorithms.
Implementing the recursive formulation of our induction step directly is nothing new. I showed you how some 
simple sorting algorithms could be implemented that way in Chapter 4, for example. The one crucial addition in 
the design method of divide and conquer is balance. This is where strong induction comes in: Instead of recursively 
implementing the step from n-1 to n, we want to go from n/2 to n. That is, we take solutions of size n/2 and build a 
solution of size n. Instead of (inductively) assuming that we can solve subproblems of size n-1, we assume that we can 
deal with all subproblems of sizes smaller than n.
1
Note that some authors use the conquer term for the base case of the recursion, yielding the slightly different ordering: divide, 
conquer, and combine.

---

Chapter 6 
■
 DiviDe, Combine, anD Conquer
116
What does this have to do with balance, you ask? Think of the weak induction case. We’re basically dividing our 
problem in two parts: one of size n-1 and one of size 1. Let’s say the cost of the inductive step is linear (a quite common 
case). Then this gives us the recurrence T(n) = T(n-1) + T(1) + n. The two recursive calls are wildly unbalanced, and 
we end up, basically, with our handshake recurrence, with a resulting quadratic running time. What if we managed to 
distribute the work more evenly among our two recursive calls? That is, could we reduce the problem to two subproblems 
of similar size? In that case, the recurrence turns into T(n) = 2T(n/2) + n. This should also be quite familiar: It’s the 
canonical divide-and-conquer recurrence, and it yields a loglinear (Q(n lg n)) running time—a huge improvement.
Figures 
6-1
 and 
6-2
 illustrate the difference between the two approaches, in the form of recursion trees. Note that 
the number of nodes is identical—the main effect comes from the distribution of work over those nodes. This may seem 
like a conjuror’s trick; where does the work go? The important realization is that for the simple, unbalanced stepwise 
approach (Figure 
6-1
), many of the nodes are assigned a high workload, while for the balanced divide-and-conquer 
approach (Figure 
6-2
), most nodes have very little work to do. For example, in the unbalanced recursion, there will 
always be roughly a quarter of the calls that each has a cost of at least n/2, while in the balanced recursion, there will be 
only three, no matter the value of n. That’s a pretty significant difference.