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

Question

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

Answer 1

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