3. (20 points) 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) = 4 T(n/4)+n/lgn.

b. T(n)=4 T(n/2) +n lgn.

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

d. T(n)-T(n-2) + n.

e. T(n)-2T(n/4) + √n.