Chapter 5

Divide and conquer refers to a class of algorithmic techniques in which one breaks the input into several parts, solves the problem in each part recursively, and then combines the solutions to these subproblems into an overall solution. Analyzing the running time of a divide and conquer algorithm generally involves solving a recurrence relation that bounds the running time recursively in terms of the running time on smaller instances.

Many common divide and conquer algorithms follow the following template: divide the input into two pieces of equal size; solve the two subproblems on these pieces separately by recursion; and then combine the two results into an overall solution, spending only linear time for the initial division and final recombining.

For any algorithm that follows the template described above let T(n) denote its worst-case running time on input instances of size n. The algorithm spends O(n) time to divide the input into two pieces of size n/2 each; it then spends time T(n/2) to solve each one (since T(n/2) is the worst-case running time for an input of size n/2); and finally it spends O(n) time to combine the solutions from the two recursive calls. Thus, we have the follow relation:

(5.1) For some constant c, T(n) ≤ 2T(n/2) + cn (where n > 2), and T(2) ≤ c.

There are two ways to solve a recurrence relation:

• “Unroll” the recursion, accounting for the running time across the first few levels, and identify a pattern that can be continued as the recursion expands. Sum the running times over all levels of the recursion (i.e., until it “bottoms out” on subproblems of constant size, thereby arriving at a total running time.
• Start with a guess for the solution, substitute it into the recurrence relation, and check that it works. Formally, one justifies this plugging-in using an argument by induction on n.

Mergesort sorts a given list of numbers by first dividing them into two equal halves, sorting each half separately by recursion, and then combining the results of these recursive calls–in the form of the two sorted halves–using a linear-time algorithm for merging sorted lists (that we discussed in Chapter 2).

We can unroll the recurrence for Mergesort as follows:

At the first level of recursion, we have a single problem of size n, which takes time at most cn plus the time spent in all subsequent recursive calls. At the next level, we have two problems each of size n/2. Each of these takes time at most cn/2, for a total of at most cn, again plus the time in subsequent recursive calls. At the third level, we have four problems each of size n/4, each taking time at most cn/4, for a total of at most cn. Therefore, at level j of the recursion, the number of subproblems has doubled j times, so there are now a total of 2^j subproblems. Each has correspondingly shrunk in size by a factor of two j times, and so each has size n/2^j, and hence each takes time at most cn/2^j. Thus level j contributes a total of at most 2^j(cn/2^j) = cn to the total running time. We know that the number of times the input must be halved in order to reduce its size from n to 2 is log n. So summing the cn work over log n levels of recursion, we get a total running time of O(n log n).