find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\mathcal{O}(n\log{n})=\Theta(f(n))$

Question

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?

Answer 1

You are right, you can't find a tight bound with those hypotheses.

I think you should interpret the question as:

find $f(n)$ for recurrence $T(n)=2T(\dfrac{n}{2})+\Theta(n\log{n})=\Theta(f(n))$

In this case, your first relation gives the right answer ($f(n) = n(\log n)^2$).

Also, as noted in the comment, your third relation is wrong, it should be $\Theta(n)$, not $\Theta(\sqrt{n})$.