The Algorithm Design Manual Second Edition

4.10.3

Solving Divide-and-Conquer Recurrences (*)

In fact, divide-and-conquer recurrences of the form T (n) = aT (n/b) + f (n) are

generally easy to solve, because the solutions typically fall into one of three distinct

cases:

1. If f (n) = O(n

log

b

a

−

) for some constant  > 0, then T (n) = Θ(n

log

b

a

).

2. If f (n) = Θ(n

log

b

a

), then T (n) = Θ(n

log

b

a

lg n).

3. If f (n) = Ω(n

log

b

a+

) for some constant  > 0, and if af (n/b)

≤ cf(n) for

some c < 1, then T (n) = Θ(f (n)).

Although this looks somewhat frightening, it really isn’t difficult to apply. The

issue is identifying which case of the so-called master theorem holds for your given

recurrence. Case 1 holds for heap construction and matrix multiplication, while

Case 2 holds mergesort and binary search. Case 3 generally arises for clumsier

algorithms, where the cost of combining the subproblems dominates everything.

The master theorem can be thought of as a black-box piece of machinery, in-

voked as needed and left with its mystery intact. However, with a little study, the

reason why the master theorem works can become apparent.

Figure

4.9

shows the recursion tree associated with a typical T (n) = aT (n/b) +

f (n) divide-and-conquer algorithm. Each problem of size n is decomposed into a

problems of size n/b. Each subproblem of size k takes O(f (k)) time to deal with

internally, between partitioning and merging. The total time for the algorithm is

the sum of these internal costs, plus the overhead of building the recursion tree.

The height of this tree is h = log

b

n and the number of leaf nodes a

h

= a

log

b

n

,

which happens to simplify to n

log

b

a

with some algebraic manipulation.

The three cases of the master theorem correspond to three different costs which

might be dominant as a function of a, b, and f (n):

• Case 1: Too many leaves – If the number of leaf nodes outweighs the sum of

the internal evaluation cost, the total running time is O(n

log

b

a

).

• Case 2: Equal work per level – As we move down the tree, each problem

gets smaller but there are more of them to solve. If the sum of the internal

evaluation costs at each level are equal, the total running time is the cost per

level (n

log

b

a

) times the number of levels (log

b

n), for a total running time of

O(n

log

b

a

lg n).

---

138

4 .

S O R T I N G A N D S E A R C H I N G

height = log n

b

partition size = 1

partition size = b

2

n

n/b

n/b

partition size = 

partition size = 

partition size = 

vertex degree = a

Figure 4.9: The recursion tree resulting from decomposing each problem of size n into a

problems of size n/b

• Case 3: Too expensive a root – If the internal evaluation costs grow rapidly

enough with n, then the cost of the root evaluation may dominate. If so, the

the total running time is O(f (n)).