2. For each part of this question, put the growth rates in order, from slowest-growing to fastest. That is, if your answer is f1(n), f2(n), . . . , fk(n), then fi(n) O(fi+1(n)) for all i. If two adjacent ones are asymptotically the same (that is, fi(n) = (fi+1(n))), you must specify this as well. Justify your answer (show your work). You may assume transitivity: if f(n) O(g(n)) and g(n) O(h(n)), then f(n) O(h(n)), and similarly for little-oh, etc. (a) Polynomials. n + 1 n 4 1 1 n 2 + 2n 4 n 2 n 10100

(b) Logarithms and related functions. (log2 n) 2 log2 (n) log3 (n) n log1.5 (n) log2 (n 2 )

(c) Logarithms in exponents. n log3 (n) n log2 n n 1/ log2 (n) n 1

(d) Exponentials. Hint: Recall Stirlings approximation, which says that n! n e n 2n, i.e. limn n! ( n e ) n 2n = 1. n! 2n 2 2n 2 n log2 (n) 2 n+

2. For each part of this question, put the growth rates in order, from slowest-growing to fastest. That is, if your answer is fi (n), f2(n),..., fr(n), then f:(n)