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