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$?
Asked
Active
Viewed 83 times
0
-
Do you know the definition of Big O? – Antonio Vargas Nov 05 '13 at 04:32
1 Answers
2
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$.
Martin Argerami
- 205,756
-
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 05 '13 at 02: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 05 '13 at 05:01