Question $2(1$ pt$.)$ Coding: write program of Quicksort. And use a sufficiently large $n,$ to measure the running time for a worst$-$case input array and an input array by shuffling the worst$-$case.

Question $3(1$pt$.)$ True or False

$n+3in(n)$

$n+3$inO$(n^2)$

$n+3in(n^2)$

$2^{n+1}$inO$(n+1)$

$2^{n+1}in(2^n)$

Question $4(1$pt$.)$ Using the master method, determine $T(n)$ for the following recurrence.

$T(n)=8T(\frac{n}{2})+n$

$T(n)=8T(\frac{n}{2})+n^2$

$T(n)=8T(\frac{n}{2})+n^3$

$T(n)=8T(\frac{n}{2})+n^4$

Question $5(1$pt$.)$ Draw recursion tree for $T(n)=8T(\frac{n}{2})+n.$ And prove the obtained T$($ n $)$ by substitution method.