1. Give asymptotic tight bounds for each of the recurrences below. Support your answer with a formal proof using the substitution method or the Master Theorem. (a) T(n) = 4T(n/3) +n (b) T(n) = 4T(n/2) + n n (c) T(n) =T(n/9) +T(2n/9) +T(2n/3) +n The master method Let a > 1 and 6 > 1 be constants, let f(n) be a function, and let T(n) be defined by the recurrence T(n) = aT(n/b) + f(n) Then T(n) has the following asymptotic bounds Case 1: If f(n) = O(nlog, a-) for some constant e > 0, then T(n) = O(nlog, a) Case 2: If f(n) = O(nlog, a), then T(n) = O(nlog, a lg n) Case 3: If f(n) = N(nlog, a+c) for some constant e > 0 and af(n/b)