Question

1. (10 Points) Fill in the blanks by selecting the statements that can be true based on the statement in the first column. g(n) grows slower g(n) grows the same g(n) grows faster than f(n) rate as fin) than f(n) f(n)-0(g(n)) f(n)=o(g(n)) f(n)=22(g(n)) f(n)-o(g(n)) f(n)=0(g(n)) 2. (10 Points) Group the following functions f1, f2, ..., f10 into different groups, so that functions within the same group grow at the same asymptotic rate. Also list groups in increasing asymptotic growth rate order. Note logn has base 10 and Ign has base 2. f1 1+ 2+ 3+ ... + (n-1) +n f2 nlogn f3 (Ign)*( Ign) f4 1 + 2 + 4 + 8 + ... +2 (n=2) f5 21gn + 100 f6 64n +32 f7 22) f8 10logn +3 19 2" f10 log(n!)

Answer 1

f(n) = O(g(n)): iff 0 <= f(n) <= c*g(n) for all n>=n, where c, no are positive constants Here we can say that if f(n) = O(g(n)) then g(n) grows faster than f(n) f(n) = o(g(n)): iff 0 <= f(n) < c*g(n) for all n>=no where c, no are positive constants Here we can say that if f(n) = o(g(n)) then g(n) grows faster than f(n) f(n) = 2(g(n)): iff 0 <= c*g(n) <= f(n) for all n>=n, where c, no are positive constants Here we can say that if f(n) = 2(g(n)) then g(n) grows slower than f(n) f(n) = (g(n)): iff 0 <= c*g(n) < f(n) for all n>=no where c, no are positive constants Here we can say that if f(n) = (g(n)) then g(n) grows slower than f(n) f(n) = (g(n)): iff 0 <= c1*g(n) <= f(n) <= c2*g(n) for all n>=n, where C1,C2, n, are positive constants Here we can say that if f(n) = (g(n)) then g(n) grows same as f(n)

fa: 1+2+3 tonnit(n-1)+ anes SI a on f2: neogn .- Oinlogn) $3: Legnja (l90) - Oliego . fu: +2+4+...+ a=1, 8=271 Sum of n terons = acrot) jinti - ti (2 ~ 2 -) = 0(2) fr. 2egn +10o = Ocean ift! 64n+32 2 Oms ft: 2120) = 0 ( 22 ) off! 10 ingots 3 Oclogn) #9: .2n - 012) fio ? Log in?) 3 or login")) looga ameogal so = Orneogn).

Increasing order of grooth Oclogn) = $.f5, follo Oliegosy) = $ 634 . OCD). >3461 Oinlogn) = 3 f2, from On - 2fil 012") d fu, fall : 012) d fty