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

Can I get an explanation of:

Can g(n) be Big O of $n^{2}$ and also the Big O of $n^{3}$? (at the same time)

Can g(n) be Big Omega of $\Omega (n)$ and also be the Big O of $n$?

share|cite|improve this question
Do you know the definition of Big O? – Antonio Vargas Nov 5 '13 at 4:32
up vote 2 down vote accepted

For your first question: if $g(n)=O(n^2)$, then $g(n)=O(n^{2+k})$ for all $k>0$. Indeed, $g(n)=O(n^2)$ means that $$ \limsup_{n\to\infty}\frac{|g(n)|}{n^2}<\infty, $$ and we also have $$ \frac{|g(n)|}{n^{2+k}}\leq\frac{|g(n)|}{n^2} $$ if $k>0$.

The answer to your second question is yes. After all, it is possible that $g(n)=n$.

share|cite|improve this answer
Did you mean to put $n^{3}$ under the lim so that it's $n^{3}$ dividing $g(n)$ in order for the the limit to go on to infinity? What does the 'sup' mean? – GivenPie Nov 5 '13 at 2:55
The limit doesn't have to exist, that's why one uses the limit superior in the defintion. Or. if you want, $g(n)$ being $O(n^2)$ means that there exist $K>0$ with $|g(n)|\leq K\,n^2$ for $n$ big enough; in that case, $n^3$ would also foot the bill. – Martin Argerami Nov 5 '13 at 5:01

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.