Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
    
Do you know the definition of Big O? –  Antonio Vargas Nov 5 '13 at 4:32

1 Answer 1

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|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

 
discard

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.