s
Section 5.5 Order of Magnitude
419
Note that the master theorem does not give exact solutions; it gives order-ofmagnitude results. Also, the value of S(1) (a constant) plays no part in determining the result.
example 47
The worst-case recurrence relation for comparisons done by the BinarySearch algorithm on a sorted list of size n (Example 30 in Chapter 3) is
C(1) = 1
C(n) = Ca
n
2
b + 1 for n ≥ 2, n = 2
m
We found the exact solution to be C(n) = 1 + log n, certainly Θ(log n). We can
find this directly from the master theorem with a = 1, b = 2, c = 0. Because
a = b
c
, C(n) = Θ(n
0
log n) = Θ(log n).
proof of the Master theorem
To prove the master theorem, we’ll go back to an expansion technique. We apply
the “recipe” of Equation (3) over and over. The recipe is that S at some value is a
times S at that value divided by b, plus that value to the c power. Therefore
S(n) = aSa
n
b
b + n
c
= a caSa
n
b
2 b + a
n
b
b
c
d + n
c
= a
2
Sa
n
b
2 b + aa
n
b
b
c
+ n
c
= a
2
caSa
n
b
3 b + a
n
b
2 b
c
d + aa
n
b
b
c
+ n
c
= a
3
Sa
n
b
3 b + a
2
a
n
b
2 b
c
+ aa
n
b
b
c
+ n
c
(
= a
k
Sa
n
b
k b + a
k−1
a
n
b
k−1 b
c
+ c + aa
n
b
b
c
+ n
c
This expansion must stop when n∙b
k
= 1, or n = b
k
, which means k = m. At that
point, using summation notation,
S(n) = a
m
S(1) + ∙
m−1
i=0
a
i
a
n
b
i b
c
= a
m
S(1) + ∙
m−1
i=0
n
c
a
a
i
b
ci b
= a
m
S(1) + n
c
∙
m−1
i=0
a
a
b
c b
i
(4)
Because n = b
m
, it follows that m = log b n, so Equation (4) can be written as
S(n) = a
log b n
S(1) + n
c
∙
m−1
i=0
a
a
b
c b
i