$1.$ By definition,

show that $1$k $+2$k $++$ nk is O$($nk$+1),$ where k is a positive integer. $(20$ points$)$

$2.$ Order the following functions into a list such that if f $($n$)$ comes before g$($n$)$ in the list then

f $($n$)=$ O$($g$($n$)).$ If any two $($or more$)$ of the same asymptotic order, indicate which. Start with these

basic functions $(10$ points$)$

n$,2$n$,$ n lg n$,$ n$3,$ lg n$,$ n $$ n$3+7$n$5,$ n$2+$ lg n

$3.$ Find the solution for each of the following recurrences, and then give tight bounds for T$($n$).(30$

points$)$

$.()=(1)+1/$ with T $(0)=0$

$.()=(1)+$ with T $(0)=1,$ where c $>1$ is some constant

$.()=(1)+1$ with T $(0)=1$

$4.$ Use the master theorem to give tight asymptotic bounds for the following recurrences. $(40$ points$)$

a$.()=2($

$2)+$n

b$.()=3($

$2)+$

c$.()=27($

$3)+3$

d$.()=5$T $($

$4)+$ c$2$

e$.()=2($

$4)+1($Bonus $10$ points$)$

f$.()=2($

$4)+$n $($Bonus $10$ points$)$