! 4096 2 1. (16 Points) True or false. (a) 5n-On) (b) n'+10n0") (c) 3n+1=0(n) (d) in=2(n) (e) n=0(5n) (f) 6n+n=0") (g) a=0(b), b>>1 (h) Ign=0(n) Hint: f(n) = Olgin)) Asymptotically, fin) "s" gin) f(n) = gn)) Asymptotically, f(n) "" g(n) f(n) = g(n)) Asymptotically, f(n) *="g) 2048 1024 512 256 128 64 32 16 log 4. log 2 1 1 3 4 S 6 7 8 2. (14 points) Is 20+1 = 0(2")? is 22- = 0(2-)? Hint: 2-1=2*2", 22=(22)=4" 3. (30 Points Using the informal definition for the notation, select the correct notation for the following expressions: a) 2(gn) + 4n+ 3n+Ign b) (6nIgn + 4) (10+n) c) [(n? +Ign)(n+1)/(n+ n) d) gen Hint: drop low order terms and leading coefficient 4. (20 Points Using the formal definition of the asymptotic notations, prove the following statements mathematically a) 10n +1 (n") b) 5+10 (n) Hint: find c and no 5. (20 points) Use the formal definition of the asymptotic notation to prove that: 30n +100 (n)