0
$\begingroup$

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<n$, 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!

$\endgroup$
1
  • $\begingroup$ 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) $\endgroup$
    – Nathaniel
    Oct 27, 2023 at 15:00

2 Answers 2

1
$\begingroup$

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}$

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Nathaniel
    Oct 27, 2023 at 15:03
0
$\begingroup$

Define S(m) = T(2^n). Write down a recursive formula for S(m) and solve it. Use the result to solve T(n).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.