Java Reference
In-Depth Information
Theorem14.1
(TheMasterTheorem)For any recurrence relation of the form
T(n) = aT(n=b) + cn
k
; T(1) = c, the following relationships hold.
8
<
:
(n
log
b
a
)
if a > b
k
(n
k
log n)
if a = b
k
T(n) =
(n
k
)
if a < b
k
.
This theorem may be applied whenever appropriate, rather than re-deriving the
solution for the recurrence.
Example14.10
Apply the Master Theorem to solve
T(n) = 3T(n=5) + 8n
2
:
Because a = 3, b = 5, c = 8, and k = 2, we find that 3 < 5
2
. Applying
case (3) of the theorem, T(n) = (n
2
).
Example14.11
Use the Master Theorem to solve the recurrence relation
for Mergesort:
T(n) = 2T(n=2) + n;
T(1) = 1:
Because a = 2, b = 2, c = 1, and k = 1, we find that 2 = 2
1
. Applying
case (2) of the theorem, T(n) = (n log n).
14.2.4
Average-Case Analysis of Quicksort
In Section 7.5, we determined that the average-case analysis of Quicksort had the
following recurrence:
n
X
1
n
T(n) = cn +
[T(k) + T(n 1 k)];
T(0) = T(1) = c:
k=0
The cn term is an upper bound on the
findpivot
and
partition
steps. This
equation comes from assuming that the partitioning element is equally likely to
occur in any position k. It can be simplified by observing that the two recurrence
terms T(k) and T(n 1 k) are equivalent, because one simply counts up from
T(0) to T(n1) while the other counts down from T(n1) to T(0). This yields
n
X
2
n
T(n) = cn +
T(k):
k=0
