Problem 4. Prove asymptotic upper and lower bounds for each of the following recurrences. Assume that in each case, the function is some positive constant for small values of n. You may assume that n = ck for some constant c that you choose. Make your bounds as tight as you can. a. T(n) = 8T(1) + nn. Hint: Use Master Theorem. c. T(n) = 16T () + (n log n). Hint: Use Master Theorem. e. T(n) = T(n-1) + nlgn. Hint: Use iterated substitution or recurrence tree method to guess T(n) it by induction. (na log n) and then prove