Recall that for the average number of comparisons for quicksort for $n$ keys we have:

$t(0)=t(1)=0,$ and $t(n)=n-1+\frac{2}{n}{\displaystyle \underset{i=2}{\overset{n-1}{}}}t(i).$

a$)$ Tabulate $t(n)$ for $n=10000,20000,30000,$dots,$1000000.$

b$)$ We have argued that $a(n)$~~$C*nlo{g}_{2}n.$ Look at the table and estimate C$.$