±.µ. Recursion Trees
the recursion tree is exactly
r
L
=
r
log
c
n
=
n
log
c
r
. Thus, the last term in the
level-by-level sum (
Σ
) is
n
log
c
r
·
f
(
1
)=
O
(
n
log
c
r
)
, because
f
(
1
)=
O
(
1
)
.
There are three common cases where the level-by-level series
(
Σ
)
is especially
easy to evaluate:
•
Decreasing:
If the series
decays exponentially
—every term is a constant
factor smaller than the previous term—then
T
(
n
)=
O
(
f
(
n
))
. In this case,
the sum is dominated by the value at the root of the recursion tree.
•
Equal:
If all terms in the series are equal, we immediately have
T
(
n
)=
O
(
f
(
n
)
·
L
)=
O
(
f
(
n
)
log
n
)
. (The constant
c
vanishes into the
O
()
notation.)
•
Increasing:
If the series
grows exponentially
—every term is a constant factor
larger than the previous term—then
T
(
n
)=
O
(
n
log
c
r
)
. In this case, the sum
is dominated by the number of leaves in the recursion tree.
In the first and third cases, only the largest term in the geometric series matters;
all other terms are swallowed up by the
O
(
·
)
notation. In the decreasing case,
we don’t even have to compute
L
; the asymptotic upper bound would still hold
if the recursion tree were infinite!
As an elementary example, if we draw out the first few levels of the recursion
tree for the (simplified) mergesort recurrence
T
(
n
)=
2
T
(
n
/
2
)+
O
(
n
)
, we
discover that all levels are equal, which immediately implies
T
(
n
)=
O
(
n
log
n
)
.
n
n
/2
n
/4
n
/4
n
/2
n
/4
n
/4
n
/8
n
/8
n
/8
n
/8
n
/8
n
/8
n
/8
n
/8
Figure ².²±.
The recursion tree for mergesort
The recursion tree technique can also be used for algorithms where the
recursive subproblems have different sizes. For example, if we could somehow
implement quicksort so that the pivot
always
lands in the middle third of the
sorted array, the worst-case running time would satisfy the recurrence
T
(
n
)
≤
T
(
n
/
3
)+
T
(
2
n
/
3
)+
O
(
n
)
.
This recurrence might look scary, but it’s actually pretty tame.
If we draw
out a few levels of the resulting recursion tree, we quickly realize that the
sum of values on any level is
at most
n
—deeper levels might be missing some
nodes—and the entire tree has depth
log
3
/
2
n
=
O
(
log
n
)
. It immediately follows
that
T
(
n
)=
O
(
n
log
n
)
. (Moreover, the number of
full
levels in the recursion
²²