Page 552 - Discrete Mathematics and Its Applications

8.3 Divide-and-Conquer Algorithms and Recurrence Relations 531

k
because a = a log n log a
b = n
b (see Exercise 4 in Appendix 2), where C 1 = f(1) + c/(a − 1)
and C 2 =−c/(a − 1).
k
Now suppose that n is not a power of b. Then b <n<b k+1 , where k is a nonnegative
integer. Because f is increasing,
f (n) ≤ f(b k+1 ) = C 1 a k+1 + C 2
≤ (C 1 a)a log n
b + C 2
= (C 1 a)n log a
b + C 2 ,
because k ≤ log n<k + 1.
b
b ).
Hence, we have f (n) is O(n log a
Examples 6–9 illustrate how Theorem 1 is used.

k
EXAMPLE 6 Let f (n) = 5f (n/2) + 3 and f(1) = 7. Find f(2 ), where k is a positive integer.Also, estimate
f (n) if f is an increasing function.

k
Solution: From the proof of Theorem 1, with a = 5, b = 2, and c = 3, we see that if n = 2 ,
then

k
f (n) = a [f(1) + c/(a − 1)]+[−c/(a − 1)]
k
= 5 [7 + (3/4)]− 3/4
k
= 5 (31/4) − 3/4.

Also, if f (n) is increasing, Theorem 1 shows that f (n) is O(n log a log 5 ). ▲
b ) = O(n
We can use Theorem 1 to estimate the computational complexity of the binary search
algorithm and the algorithm given in Example 2 for locating the minimum and maximum of a
sequence.

EXAMPLE 7 Give a big-O estimate for the number of comparisons used by a binary search.

Solution: In Example 1 it was shown that f (n) = f (n/2) + 2 when n is even, where f is the
number of comparisons required to perform a binary search on a sequence of size n. Hence,
from Theorem 1, it follows that f (n) is O(log n). ▲

EXAMPLE 8 Give a big-O estimate for the number of comparisons used to locate the maximum and minimum
elements in a sequence using the algorithm given in Example 2.

Solution: In Example 2 we showed that f (n) = 2f (n/2) + 2, when n is even, where f is the
number of comparisons needed by this algorithm. Hence, from Theorem 1, it follows that f (n)
is O(n log 2 ) = O(n). ▲

We now state a more general, and more complicated, theorem, which has Theorem 1 as
a special case. This theorem (or more powerful versions, including big-Theta estimates) is
sometimes known as the master theorem because it is useful in analyzing the complexity of
many important divide-and-conquer algorithms.