Derive solutions to the following recurrences. A solution should include$-$the tightest upper and lower bounds that the recurrence will allow. Assume $T(1)=(1).$

Solve parts $($a$),($b$),$ and $($c$)$ in two ways: drawing a recursion tree and applying Master Theorem. Free to choose methods for part $($d$).$

$($a$)$

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

$($b$)$

$T(n)=3T(\frac{n}{\sqrt[\phantom{2}]{2}})+O(n^4)$

$($c$)$

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

$($d$)$

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