Computing time complexity

If we have an algorithm such that its complexity is $\Theta(m + n^2)$ and we know that $0 < m < n^2$, then its complexity becomes $\Theta(n^2)$. But if we had an algorithm such that its complexity was $\Theta(m\log n)$ and $0 < m < n^2$, could we conclude that its complexity is $\Theta(n^2\log n)$?

-

migrated from cstheory.stackexchange.comDec 26 '12 at 13:31

This question came from our site for theoretical computer scientists and researchers in related fields.

This is not a research level question, though a nice exercise for an undergraduate course. Please check cstheory.stackexchange.com/faq for more information. –  Yixin Cao Dec 26 '12 at 12:26
yes. Reread the definition of the $O$ notation. There are many posts in cs.stackexchange.com with similar content. –  AJed Dec 26 '12 at 16:48
@AJed The OP is asking about $\Theta$ (not $O$), which also requires $\Omega$ notation. That is probably why Yixin calls it a nice exercise. I believe the answer is actually no because of the lower bound. –  mayank Dec 26 '12 at 17:34
@mayank oh yes, I didnt see this. –  AJed Dec 26 '12 at 20:19

If $m=\Theta(n^2)$, then indeed $\Theta(m\log n)=\Theta(n^2\log n)$.
However, you are only given that $0<m<n^2$, that is, $m=O(n^2)$ and you can only infer that the algorithm has complexity $O(n^2 \log n)$, but not $\Theta$ of the same quantity. For instance, assume $m$ is a constant, or assume $m=\sqrt{n}$, and you could see why it cannot be $\Theta(n^2\log n)$.