We have recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$ and assume $T(1)$ is a constant. Find asymptotically tight bounds $\Theta(f(n))$ for $T(n)$.
There's something that confuses me. We know $\{n\log{n}, n, \sqrt{n}\}\subset \mathcal{O}(n\log{n})$. So with Master Theorem applied:
- if $T(n)=2T(\dfrac{n}{2})+n\log{n}$, then $T(n)=\Theta(n\log^2{n})$
- if $T(n)=2T(\dfrac{n}{2})+n$, then $T(n)=\Theta(n\log{n})$
- if $T(n)=2T(\dfrac{n}{2})+\sqrt{n}$, then $T(n)=\Theta(\sqrt{n})$
If its asymptotically tight bounds varies, then how can we provide a asymptotically tight bounds for $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})$? If we can, how? Can we prove it using induction?