# Does $\Theta(m \log n)$ and $0 < m < n^2$ imply $\Theta(n^2 \log n)$?

From a function in $\Theta(m + n^2)$ and $0 < m < n^2$, We conclude it is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ so that $0 < m < n^2$, imply that it is in $\Theta(n^2\log n)$?

-
What does $\theta$ notation mean? – Godot Dec 26 '12 at 13:37
@Godot: I suppose that should actually be $\Theta$, not $\theta$. – Ilmari Karonen Dec 26 '12 at 14:58

I assume that, by $\Theta$, you mean this notation.
From $f(m,n) \in \Theta(m \log n)$ and $0 < m < n^2$, we can conclude that $f(m,n) \in O(n^2 \log n)$. We cannot conclude $f(m,n) \in \Theta(n^2 \log n)$, since it's possible that $m \in o(n^2)$. For example, if $m = n$, then $f(m,n) \in \Theta(n \log n)$.
The reason we could conclude from $f(m,n) \in \Theta(m + n^2)$ and $0 < m < n^2$ that $f(m,n) \in \Theta(n^2)$ is that, even if $m \in o(n^2)$, the expression $m + n^2$ still contains an $n^2$ term which will dominate any smaller $m$. That is, we already know that $\Theta(m + n^2) \subset \Omega(n^2)$, and $m < n^2$ implies that $\Theta(m + n^2) \subset O(n^2)$, and thus $\Theta(m + n^2) \subset (\Omega(n^2) \cap O(n^2)) = \Theta(n^2)$.
However, if we know that $m \in \Theta(n^2)$, then we can indeed conclude from $f(m,n) \in \Theta(m \log n)$ that $f(m,n) \in \Theta(n^2 \log n)$.