$$

alt

uarr shift

alt

$2-$ What is $6n^3+5n^2+2$ in big$-$Oh term? Prove it using the related inequality. $[1$ point$]$

$3-$ Write a recurrence relation for the running time of $g(n)$ and solve that recurrence using Master method. Assume that addition can be done in constant time. $[2$ points$]$

defg$(n)$ :

if $n==1$ :

return $1$

else:

$x=g(\frac{n}{4})$

return $x+x$

$4-$ Apply Counting Sort on the sequence of $2,3,3,5,6,7,8,7,8,5,7,4,2.[2$ points$]$