# What can be said about Θ-classes in m and n if we know that m < n?

A function in $\Theta(m + n^2)$ and $0 < m < n^2$, is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ and $0 < m < n^2$, imply that it 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.

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

-