Question $5.$ Please solve the following recurrences using substitution method. After that used Master Theorem to verify.

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

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

$T(n)=4T(\frac{n}{2})+n^{2\mathrm{.}5}$

$T(n)=T(n-1)+1$

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

$T(n)=T(\frac{n}{2})+T(\frac{n}{4})+n($Bonus points for this one$)$