Description
Problem 1 (25pts)
Do Problem 2.3-3 on page 39 in CLRS. Justify your answers.
Problem 2 (25pts)
- Rank the following functions by order of growth; that is, find an ar-rangement f1, f2, ··· , f24of 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
- 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
