Question 3

$$T(n)=4\cdot T\left(\begin{array}{c}\lceil \frac{n}{4}\rceil \end{array}\right)+2n$$

And $T(0)=1$ and $T(1)=1$.

Show that $T(n)\ge 2n{\log }_{2}n+(2n-1)$ for all $n\ge 1$:

1. Base Case: Show that $T(n)\ge 2n{\log }_{2}n+(2n-1)$ for $n=1$:

$$\begin{array}{rl}T(n)& \ge ?2n{\log }_{2}n+(2n-1)\\ 1& \ge ?2\cdot 0+2-1\\ 1& \ge 1\text{ as required}\end{array}$$

2. Inductive Case: Assume that $T(m)\ge 2m{\log }_{2}m+(2m-1)$ for all $m\le k$ for some $k\ge 1$. We need to show that $T(k+1)\ge 2(k+1){\log }_2(k+1)+(2(k+1)-1)$. Or otherwise, $T(k+1)\ge 2(k+1){\log }_2(k+1)+(2k+1)$. We then have that for $n=k+1$:

$$\begin{array}{rl}T(k+1)& =2\cdot T\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)+2(k+1)\\ & \ge 2\cdot \left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)\cdot {\log }_2\left(\begin{array}{c}\lceil \frac{k+1}{2}\rceil \end{array}\right)+2(k+1)\\ & \ge 2\cdot \left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)\cdot {\log }_2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)+2(k+1)\\ & =(k+1){\log }_2\left(\begin{array}{c}\frac{k+1}{2}\end{array}\right)+(2k+2)\\ & \ge 2(k+1){\log }_2(k+1)+(2k+1)\text{ as required}\end{array}$$

Hence, by strong induction, $T(n)\ge 2n{\log }_{2}n+(2n-1)$ for all $n\ge 1$.