# Prove $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(n\log^2{n})$ using induction

Please first take a brief look at my previous question. Here I want to do something similar but for $$T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})$$. I know the answer is $$T(n)=\Theta(n\log^2{n})$$ and I want to prove it using induction. I reached this assuming for $$m, we have $$T(m)\leq cm\log^2{m}$$:

\begin{align*} T(n)=2T(\frac{n}{2})+\Theta(n\log{n})&\leq 2(c\dfrac{n}{2}\log^2{\frac{n}{2}})+\Theta(n\log{n})\\ &= cn(\log{n}-1)^2+\Theta(n\log{n})\\ &=cn(\log^2n-2\log{n}+1)+\Theta(n\log{n})\\ &=cn\log^2n+cn-2cn\log{n}+\Theta(n\log{n}) \end{align*}

At this point I can't go further. Also maybe we can reach $$T(n)\leq cn\log^2n+cn+\Theta(n\log{n})$$. But how can I reach $$T(n)\leq cn\log^2n$$? I tried to use stronger induction hypothesis like $$T(m)\leq cm\log^2m-dm$$ but I couldn't succeed. How can I show that? Any help is appreciated!

• When doing such a proof, you should get rid of the $\Theta$, since it hides information, and can be a source of error (see this post) Commented Oct 27, 2023 at 15:00

Let $$c$$ be the constant for the $$\Theta$$ expression, and show that $$T(n) \leq c n \log^2 n$$.
By induction, assume $$n \geq 2$$.
\begin{align} T(n) &= 2T(n/2) + cn \log n\\ &\leq 2(c \frac n 2 \log^2 \frac n 2)) + cn \log n \text{ (by I.H.)}\\ &= cn \log \frac n 2 \log \frac n 2 + c n \log n\\ &= cn (\log n - 1)(\log n - 1) + cn \log n\\ &= cn (\log^2 n - 2\log n + 1) + cn \log n\\ &= cn \log^2 n - 2cn\log n + cn + cn \log n\\ &= cn \log^2 n - cn\log n + cn\\ &= cn \log^2 n + cn (1- \log n)\\ &\leq cn \log^2 n \end{align}
• Actually, you proved that $T(n) =\mathcal{O}(n(\log n)^2)$, not $\Theta$. You should add a comment that the lower bound can be found similarly. Commented Oct 27, 2023 at 15:03