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?


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


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.