Page 551 - Discrete Mathematics and Its Applications

530 8 / Advanced Counting Techniques

k
Because n/b = 1, it follows that

k−1

k j j
f (n) = a f(1) + a g(n/b ).
j = 0
We can use this equation for f (n) to estimate the size of functions that satisfy divide-and-conquer
relations.

THEOREM 1 Let f be an increasing function that satisfies the recurrence relation

f (n) = af (n/b) + c

whenever n is divisible by b, where a ≥ 1, b is an integer greater than 1, and c is a positive
real number. Then

log a
O(n b ) if a> 1,
f (n) is
O(log n) if a = 1.

k
Furthermore, when n = b and a = 1, where k is a positive integer,
log a
f (n) = C 1 n b + C 2 ,

where C 1 = f(1) + c/(a − 1) and C 2 =−c/(a − 1).

k
Proof: First let n = b . From the expression for f (n) obtained in the discussion preceding the
theorem, with g(n) = c,wehave

k−1 k−1

k j k j
f (n) = a f(1) + a c = a f(1) + c a .
j = 0 j = 0
When a = 1wehave

f (n) = f(1) + ck .

k
Because n = b ,wehave k = log n. Hence,
b
f (n) = f(1) + c log n.
b
k
When n is not a power of b,wehave b <n<b k+1 , for a positive integer k. Because f is
increasing, it follows that f (n) ≤ f(b k+1 ) = f(1) + c(k + 1) = (f (1) + c) + ck ≤ (f (1) +
c) + c log n. Therefore, in both cases, f (n) is O(log n) when a = 1.
b
k
Now suppose that a> 1. First assume that n = b , where k is a positive integer. From the
formula for the sum of terms of a geometric progression (Theorem 1 in Section 2.4), it follows
that
k
k
f (n) = a f(1) + c(a − 1)/(a − 1)
k
= a [f(1) + c/(a − 1)]− c/(a − 1)
b + C 2 ,
= C 1 n log a