1. If f(n) = (g(n)) then is g(n) = Big O(f(n))? For an algorithm, what is (i) the worst case time complexity, (ii) the average case time complexity, and (iii) the best case time complexity? Which one is critical?

2. Poly(n,k) is the kth degree polynomial in n. Prove that Poly(n,k) is (n^k).

3. Prove that ^k where ranges from 1 to n is (n^k+1).

Transcribed image text