Data Structures and Algorithms. You must justify your answer. When describing an algorithm, analyze its running time and explain why the algorithm is correct.

1. Prove that T(n) = 3n^4 + 7n^3 + 50 = O(n^4 )

2. If f(n) = n^3 and g(n) = 17,000,000n^2. Prove that g(n) = O(f(n))

3. If f(n) = 3n^2 and g(n) = 17,000,000 n^2 Prove that f(n) = O(g(n))

4. f(n) = n^0.000000001 , g(n) = (logn)^1,000,000. Is g(n) = O(f(n))? Why?

5. If f(n) = lgn^0.0000001 and g(n) = (logloglogn)^3,000,000. Which one grows faster? Why?