Introduction to Algorithms, Third Edition

polynomial-growth condi-
tion
: there exist positive constants
c
1
and
c
2
such that for all
x
1
, for
i
D
1; 2; : : : ; k
, and for all
u
such that
b
i
x
u
x
, we have
c
1
f .x/
f .u/
c
2
f .x/
. (If
j
f
0
.x/
j
is upper-bounded by some polynomial in
x
, then
f .x/
satisfies the polynomial-growth condition. For example,
f .x/
D
x
˛
lg
ˇ
x
satisfies this condition for any real constants
˛
and
ˇ
.)
Although the master method does not apply to a recurrence such as
T .n/
D
T .
b
n=3
c
/
C
T .
b
2n=3
c
/
C
O.n/
, the Akra-Bazzi method does. To solve the re-
currence (4.30), we first find the unique real number
p
such that
P
k
i
D
1
a
i
b
p
i
D
1
.
(Such a
p
always exists.) The solution to the recurrence is then
T .n/
D
‚
x
p
1
C
Z
x
1
f .u/
u
p
C
1
du
:
The Akra-Bazzi method can be somewhat difficult to use, but it serves in solving
recurrences that model division of the problem into substantially unequally sized
subproblems. The master method is simpler to use, but it applies only when sub-
problem sizes are equal.

---

5
Probabilistic Analysis and Randomized
Algorithms
This chapter introduces probabilistic analysis and randomized algorithms. If you
are unfamiliar with the basics of probability theory, you should read Appendix C,
which reviews this material. We shall revisit probabilistic analysis and randomized
algorithms several times throughout this book.