Algorithm Design

Show all steps and explain clearly. No points for insufficient reasoning.

Problem 4. (30 points) Give asymptotic upper and lower bounds for T(n) in each of the following recurrences. Assume that Tin) is constant for sufficiently small n. Make your bounds as tight as possible, and justify your answers. c) T(n) = T(n/2) +T(n/4) + T[n/8) +n