Computing time complexity

Question

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

Answer 1

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