Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
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
up vote 3 down vote accepted

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

share|cite|improve this answer
Yes as you guess it's big theta. Tnx for your clear and complete explanation. I will vote up as soon as i get 15 reputation. – Sajjad Dec 26 '12 at 16:37

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.