$20\%$ Solve each of the following recurrences

$($Note that you need to self$-$study the techniques mentioned in Slide $5$ of the

"divide$-$and$-$conquer" set of slides.$)$

$($a$)$ Show that the solution of $T(n)=T(|$~$\frac{n}{2}$~$|)+1$ is $O(logn),$ where $|$~$x$~$|$ is the

ceiling of $x,$ i$.$e$.,$ the smallest integer $y$ such that $yx.$

$($b$)$ Draw the recursive tree for $T(n)=4T({|}_{{?}_{?}}\frac{n}{2_{{?}_{?}}}|)+cn,$ where c is a constant,

and provide a tight asymptotic bound on its solution. Verify your bound

by the substitution method.

$($c$)$ Show that the solution of $T(n)=aT(\frac{n}{b})+c{n}^p,$ where $c$ is a constant, $a,b,$

$p$ are integers, and $a=b^p,a1,b2,p0$ is $(n^{p}logn).$ In this

part, you can assume that $n=b^k$ for some integer $k.$