$1.(12$ pts$)$ Use the substitution method to show that each of the following recurrences defined has

the asymptotic solution specified:

a$.$ T$($n$)=$ T$($n$-1)+$ n has solution T$($n$)=$ O$($n$2).$

b$.$ T$($n$)=$ T$($n$/2)+\backslash$Theta $(1)$ has solution T$($n$)=$ O $($lg n$).$

c$.$ T$($n$)=2$T$($n$/2)+$ n has solution T$($n$)=\backslash$Theta $($n lg n$).$

d$.$ T$($n$)=2$T $($n$/2+17)+$ n has solution T$($n$)=$ O $($n lg n$).$

e$.$ T$($n$)=2$T$($n$/3)+\backslash$Theta $($n$)$ has solution T$($n$)=\backslash$Theta $($n$).$

f$.$ T$($n$)=4$T$($n$/2)+\backslash$Theta $($n$)$ has solution T$($n$)=\backslash$Theta $($n$2).$

$2.(8$ pts$)$ For each of the following recurrences, sketch its recursion tree, and guess a good

asymptotic upper bound on its solution. Use the substitution method to verify your answer.

a$.$ T$($n$)=$ T$($n$/2)+$ n$3$

b$.$ T$($n$)=4$T$($n$/3)+$ n$.$

c$.$ T$($n$)=4$T$($n$/2)+$ n$.$

d$.$ T$($n$)=3$T$($n$-1)+1.$

$3.(10$ pts$)$ Use the master method to give tight asymptotic bounds for the following recurrences.

a$.$ T$($n$)=2$T$($n$/4)+1.$

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

c$.$ T$($n$)=2$T$($n$/4)+$ lg$2$ n$.$

d$.$ T$($n$)=2$T$($n$/4)+$ n$.$

e$.$ T$($n$)=2$T$($n$/4)+$ n$2.$

$4.(12$ pt$)$ Give the asymptotically tight upper and lower bounds for T$($n$)$ in each of the following

algorithmic recurrences. Justify your answers.

a$.$ T$($n$)=2$T$($n$/2)+$ n$3$

b$.$ T$($n$)=$ T$(8$n$/11)+$ n$.$

c$.$ T$($n$)=16$T$($n$/4)+$ n$2.$