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

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?

• For your third case, how are you getting $\Theta(\sqrt{n})$ from the master theorem? I would think that a recurrence relation with the first term $2T(n/2)$ will never be smaller than $\Theta(n)$, even if the second term is zero. Commented Oct 25, 2023 at 1:18
• – D.W.
Commented Oct 27, 2023 at 19:01

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