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

I) T(n) = 2T(n/2) + n^4

II) T(n) = 16T(n/4) + n^2

III) T(n) = T(n-2) + n^2

IV) T(n) = 2T(n/4) + n