Solve ALL OF the following recurrences and provide explanations. Hint: Generously apply the master theorem.

Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that T(n) is constant for n 2. Make your bounds as tight as possible, and justify your answers.

a. T(n) = 2T(n/2) + n3

b. T(n) = T(9n/10) + n

c. T(n) = 16T(n/4) + n2

d. T (n) = 7T(n/3) + n2

e. T(n) = 7T(n/2) + n2

f. T(n) = 2T(n/4) + n1/2

g. T(n) =T(n-1) + n

h. T(n) = T(n1/2) + 1

(Master theorem) Leta 2 1 and b> I be constants, let f(n) be a function, and let T(n) be defined on the nonnegative integers by the recurrence T(n) = aT(n/b) + f(n) . where we interpret n/b to mean either In/born/b]. Then T(n) has the follow- ing asymptotic bounds: I. If f(n)O(n-) for some constant e > 0, then T(n) e(n) 2. If f(n) (nlogba), then T(n) = (nlog, a Ign). 3. If f(n) 2(no') for some constant e 0, and if af(n/b) S cf(n) for logh a some constant c