QUESTION 2, 4(b), 5, 6, 7(a) &(b) !!!!!!!! URGENT

ATLEAST 2 and 6

2. (16 pts) Rank the following functions by the order of growth rate (that is, list them in a list fi(n), f2(n), f3(n), . .. such that fi(n) = O(f2(n)), f2(n) = O(f3(n)), ...). Partition your list into equivalent classes such that f (n) and g(n) are in the same class if and only if f (n) = O(g(n)). You must prove your answer (by limit test or other means). (V3)1083 , n2, In2n2, InInn, (Inn)Inn, ninlun, 418, nlg2n, n!, (n -1)!, (4/3)", n/2 Note: Ig is the log function with base 2. In is the log function with base e. Ig n means (lgn)2; In' n2 means (Inn2)2 4 (b) Using Stirling's formula, prove Cn = 0 (73/z). 5. (2+3=5 pts) Give asymptotically tight bounds of the following summations (by using integral method.) (a) ER_1 K1.5 - 2k + 3 (b) Ek=n/2 k Ink 6. (9 pts) Give the asymptotic lower and upper bounds for T(n) in each of the following recurrences. Assume that T(n) is a constant for n is defined by: ao = 1, a1 = 3 and, for n 2 2, an = 4an-1 - 3an-2. Find the closed form for an. (b) The sequence is defined by: bo = 1, b1 = 2, b2 = 13 and, for n 2 3, bn = 3bn-2 + 2bn-3. Find the closed form for bn