Description
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 arrangement 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
3
)n n2 + n (
3
4
)n lg(n!) 22n
n1/ lg n
lnlnn 2n n2n nn lnn n lg n
2lg n (lg n)lg n n √lg n 1 lg∗(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