$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$)$

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

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

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

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

a$.$ T$($n$)=2$T $($n$2)+$ sqrt$($n$)$

b$.$ T$($n$)=3$T $($n$2)+$ cn

c$.$ T$($n$)=27$T $($n$3)+$ cn$3$

d$.$ T$($n$)=5$T $($n$4)+$ cn$2$

e$.$T$($n$)=2$T $($n$4)+1($Bonus $10$ points$)$

f$.$ T$($n$)=2$T $($n$4)+$ sqrt$($n$)($Bonus $10$ points$)$