Ordering by asymptotic growth rates a. Rank the following functions by order of growth; that is, find an arrangement g1; g2;:::;g30 of the functions satisfying g1 D .g2/, g2 D .g3/, ..., g29 D .g30/. Partition your list into equivalence classes such that functions f .n/ and g.n/ are in the same class if and only if f .n/ D .g.n//. lg.lg n/ 2lg n . p2/lg n n2 n .lg n/ . 3 2 /n n3 lg2 n lg.n/ 22n n1= lgn ln ln n lg n n 2n nlg lg n ln n 1 2lg n .lg n/lg n en 4lg n .n C 1/ plg n lg .lg n/ 2p2 lg n n 2n n lg n 22nC1 b. Give an example of a single nonnegative function f .n/ such that for all functions gi.n/ in part (a), f .n/ is neither O.gi.n// nor .gi.n//.

L20 - 6 Recall the following: If x>d0a y> 0, 1. ln(xy)= ▯ ▯ x 2. ln = y y 3. ln(x )= We can use these properties to write a complicated logarithmic function into a form involving sums and diﬀerences, which are easier to diﬀerentiate. ▯ x +2 x ex. Find f (x)i f(x)=n l . 2x − 6