The Proof For Exact Powers

The proof for exact powers: The first part of the proof of the master theorem analyzes the recurrence (4.5)

T (n) = aT (n/b) f (n),

for the master method, under the assumption that n is an exact power of b > 1, where b need not be an integer. The analysis is broken into three lemmas. The first reduces the problem of solving the master recurrence to the problem of evaluating an expression that contains a summation. The second determines bounds on this summation. The third lemma puts the first two together to prove a version of the master theorem for the case in which n is an exact power of b.

Lemma 4.2 : Let a ≥ 1 and b > 1 be constants, and let f (n) be a nonnegative function defined on exact powers of b. Define T (n) on exact powers of b by the recurrence

Proof : We use the recursion tree in Figure 4.3. The root of the tree has cost f (n), and it has a children, each with cost f (n/b). (It is convenient to think of a as being an integer, especially when visualizing the recursion tree, but the mathematics does not require it.) Each of these children has a children with cost f (n/b2), and thus there are a2 nodes that are distance 2 from the root. In general, there are aj nodes that are distance j from the root, and each has cost f (n/bj). The cost of each leaf is T (1) = Θ(1), and each leaf is at depth logb n, since . There are leaves in the tree.

Figure 4.3: The recursion tree generated by T (n) = aT (n/b) f (n). The tree is a complete a-ary tree with  leaves and height logb n. The cost of each level is shown at the right, and their sum is given in equation (4.6).

We can obtain equation (4.6) by summing the costs of each level of the tree, as shown in the figure. The cost for a level j of internal nodes is aj f(n/bj), and so the total of all internal node levels is

In the underlying divide-and-conquer algorithm, this sum represents the costs of dividing problems into subproblems and then recombining the subproblems. The cost of all the leaves, which is the cost of doing all  subproblems of size 1, is .

In terms of the recursion tree, the three cases of the master theorem correspond to cases in which the total cost of the tree is (1) dominated by the costs in the leaves, (2) evenly distributed across the levels of the tree, or (3) dominated by the cost of the root.

The summation in equation (4.6) describes the cost of the dividing and combining steps in the underlying divide-and-conquer algorithm. The next lemma provides asymptotic bounds on the summation's growth.