a) Prove that running time T(n)=n3+30n+1 is O(n3) [1 mark]

b) Prove that running time T(n)=(n+30)(n+5) is O(n2) [1 mark]

c) Count the number of primitive operation of algorithm unique1 on page 174 of textbook, give a big-Oh of this algorithm and prove it. [2 mark]

d) Order the following function by asymptotic growth rate [2 mark]

a. 4nlogn+2n

b. 210

c. 3n+100logn

d. n2+10n

e. n3 f. nlogn