Why is $T(n)=2T\left(\frac{n}{2}\right) + n\log(n)$ time complexity is $Θ\big( n\log^2(n) \big) $?

Question

I was doing some homework and worked out a closed form for $T(n) = 2T\left(\frac{n}{2}\right) + n\log(n)$ and got:

$T(n)=n+n\left(\log(n)+\log\left(\frac{n}{2}\right)+\log\left(\frac{n}{4}\right)+\log\left(\frac{n}{8}\right)+\cdots+ 1\right)$

as closed form.

I was able to prove that $T(n)$ is in big O of $n\log^2(n)$ by:

$T(n) < n + n\log(n)\leq a\log^2(n)$ for some constant $a\geq 1$

But I don't know how $T(n)$ is in big omega of $n\log^2(n)$ since I have to go the other way and cannot see how:

$T(n)\geq a\log^2(n)$

in order to prove that $T(n)$ is in big omega of $n\log^2(n)$ and therefore in big theta of $n\log^2(n)$.

Am I missing something here?

Answer 1

Let $k = \lfloor \frac12 \log n\rfloor$, which is $\Omega(\log n)$. Then if we just take the first $k+1$ terms of the sum, that is $$ \log n + \log \frac n2 + \log \frac n4 + \dots + \log \frac n{2^k}, $$ we already get something that's $\Omega(\log^2 n)$.

That's because $\frac{n}{2^k} \ge \sqrt n$, so $\log \frac{n}{2^k} \ge \log \sqrt{n} = \frac12 \log n$, which is $\Omega(\log n)$ - and that's the smallest term. Summing $\Omega(\log n)$ terms, on which we have an $\Omega(\log n)$ lower bound, we get $\Omega(\log^2 n)$.

Answer 2

$$ \bbox[7px,border:2px solid red] {\text{MASTER THEOREM}}: $$

$$T(n)=aT(n/b)+f(n).$$ $$\bbox[1px,border:1px solid green] {a\ge 1,b>1,f(n)=Θ\big( n^k\cdot \log^p(n)\big)}$$ $$\text{CASE 1}:$$

$$ \text{if } \log_b(a)>k\text{ then: }\quad \bbox[0.2px,border:0.8px solid black] {T(n)=Θ\big( n^{\log_b(a)}\big)} $$

---

$$\text{CASE 2}:$$

$$\text{if } \log_b(a)=k:\begin{cases} \text{if $p>-1:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot \log^{p+1}(n)\big)}$} \\ \text{if $p=-1:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot \log\big( \log(n)\big)\big)} $ }\\ \text{if $p<-1:\quad \bbox[1px,border:1.5px solid black] {T(n)=Θ\big( n^k\big)}$ }\\ \end{cases} $$

---

$$\text{CASE 3}:$$

$$\text{if $\log_b(a)<k:\begin{cases} \text{if $p\ge 0:\quad \bbox[1px,border:1px solid black] {T(n)=Θ\big( n^k\cdot\log^p(n)\big)} $} \\ \text{if $p<0:\quad \bbox[0.5px,border:0.2px solid black] {T(n)=\mathcal O \big( n^k\big)} $} \end{cases}$}$$

---

$$\text{So, let }a=b=2,f(n)=Θ\big( n^1\cdot \log^1(n)\big) \Rightarrow k=p=1,$$ $$\log_2(2)=1=k\text{ we are in case 2, where $p=1>-1$ hence,}$$ $$T(n)=Θ\big( n^k\cdot \log^{p+1}(n)\big)=\bbox[3px,border:2px solid green] {Θ\big( n\cdot \log^{2}(n)\big)}. $$