Java Reference
In-Depth Information
= a
m
T(1) + a
m1
c(n=b
m1
)
k
+ + ac(n=b)
k
+ cn
k
= a
m
c + a
m1
c(n=b
m1
)
k
+ + ac(n=b)
k
+ cn
k
X
a
mi
b
ik
= c
i=0
= ca
m
X
i=0
(b
k
=a)
i
:
Note that
a
m
= a
log
b
n
= n
log
b
a
:
(14.1)
The summation is a geometric series whose sum depends on the ratio r = b
k
=a.
There are three cases.
1. r < 1: From Equation 2.4,
X
r
i
< 1=(1 r); a constant:
i=0
Thus,
T(n) = (a
m
) = (n
log
b
a
):
2. r = 1: Because r = b
k
=a, we know that a = b
k
.
From the definition
of logarithms it follows immediately that k = log
b
a.
We also note from
Equation 14.1 that m = log
b
n. Thus,
X
r = m + 1 = log
b
n + 1:
i=0
Because a
m
= n log
b
a = n
k
, we have
T(n) = (n
log
b
a
log n) = (n
k
log n):
3. r > 1: From Equation 2.5,
m
X
r =
r
m+1
1
r 1
= (r
m
):
i=0
Thus,
T(n) = (a
m
r
m
) = (a
m
(b
k
=a)
m
) = (b
km
) = (n
k
):
We can summarize the above derivation as the following theorem, sometimes
referred to as the Master Theorem.
