SKEDSOFT
Substituting this expression for the summation in equation (4.9) yields
and case 2 is proved.
Case 3 is proved similarly. Since f(n) appears in the definition (4.7) of g(n) and all terms of g(n) are nonnegative, we can conclude that g(n) = Ω(f(n)) for exact powers of b. Under our assumption that af(n/b) ≤ cf(n) for some constant c < 1 and all n ≥ b, we have f(n/b) ≤ (c/a)f(n). Iterating j times, we have f(n/bj) ≤ (c/a)j f(n) or, equivalently, aj f(n/bj) ≤ cj f(n). Substituting into equation (4.7) and simplifying yields a geometric series, but unlike the series in case 1, this one has decreasing terms:
since c is constant. Thus, we can conclude that g(n) = Θ(f(n)) for exact powers of b. Case 3 is proved, which completes the proof of the lemma.
We can now prove a version of the master theorem for the case in which n is an exact power of b.
Lemma 4.4
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
where i is a positive integer. Then T(n) can be bounded asymptotically for exact powers of b as follows.
-
If
for some constant ∈> 0, then 
. -
If
, then 
. -
If
for some constant ∈> 0, and if af (n/b) ≤ cf(n) for some constant c < 1 and all sufficiently large n, then T(n) = Θ(f(n)).
ProofWe use the bounds in Lemma 4.3 to evaluate the summation (4.6) from Lemma 4.2. For case 1, we have
