Problem 1 (25pts)
Do Problem 2.3-3 on page 39 in CLRS. Justify your answers.
Problem 2 (25pts)
1. Rank the following functions by order of growth; that is, find an ar-rangement f1, f2, ··· , f24 of the functions satisfying f1 = O(f2), f2 = O(f3), ··· , f23 = O(f24). Briefly show your work for this problem.
lg(lg∗ n)
nlg lg n
nlog6 5
n2
n!
22n
(
4
)n
n2 + n
(
3
)n
lg(n!)
22n
n1/ lg n
3
4
2n
nn
lnlnn
n2n
lnn
n lg n
2lg n
(lg n)lg n
n
√
1
lg∗(lg n)
lg n
1
2. Partition your list into equivalence classes such that f (n) and g(n) are in the same class if and only if f (n) = Θ(g(n)).
Problem 3 (50pts)
Do Problem 4-3 (a) to (e) on page 108 in CLRS. Justify your answers.
2
