CSCI 36200: Data Struc Problem Set 1 Instructor: Dr. Snehasis Mukhopadhyay D 1. Prove or disprove the following statements: (i) n! = 0(n") (ii) na log n = O(n?) (iii) 2n + n20 = 0(3) (iv) 2n2 + nlogn = m(n) + Big (v) n1.001 + n log n = O(n log ny (vi) n1+2/Vlogn = O(n log n) (viii) (n+1)+logn 2n (vii) log n + log n2 + log n3 = (log n) En = O(log n) + Big (ix) (n+1) logn = O(logn) (x) log log logn = O(log n1/3) 2. A fast exponentiation function is given below