Rank the following functions by order of growth; that is, find an arrangement g1, g2, ..., g8 of the functions satisfying g1 = O(g2), g2 = O(g3), ..., g7 = O(g8). Justify your ordering. (log n)^3 , n^(log log n) , n^(1+1/ log n) , 4^logn , n!, 2^(sqrt(2logn)) , n^2 , (1.1)^n Note: By log n, we mean log2 n, unless otherwise stated. Note that log3 n is the usual way of writing (log n) 3 . (Hint: Use the limit definition of Big-O and Big-Theta. See the hint for Exercise 2.2.)

Hint: Note: By log n, we mean log2 n, unless otherwise stated. Note that log10 n is the usual way of writing (log n) 10 . (Hints: (1) When comparing functions of the form f g it might be helpful to compare the logarithm of those functions, i.e., log f g = g log f. n! = n(n 1). . .(2)(1) which you can use to lower or upper bound n! , e.g., 2.6. EXERCISES 29 2 n < n! < nn , for all n > 4. (2) Use the limit definition of the Big-O notation. You might want to recall the LHopitals rule for computing the limit of the ratio of two functions. The L Hopitals rule states the following: If limxa f(x)/g(x) evaulates to an indeterminate form such as 0/0 or /, then limxa f(x)/g(x) = limxa f 0 (x)/g0 (x). Here a can be any number and f 0 and g 0 are the derivatives of f and g respectively.)