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.

if $a=O(N^2) $ then according to the big oh definition I didn't see why we can't say $a= O(N^4)$ or $= O(N^8)$

share|improve this question
    
One small caveat: you can say this as long as you're referring to the behavior as $N\to\infty$ - which is generally assumed since you're talking about $N$, but not explicit in the notation. Note that saying that $a\in O(x^2)$ as $x\to 0$ does not imply that $a\in O(x^4)$ then! –  Steven Stadnicki Feb 4 '13 at 17:03
    
I think the reason many people get confused with "big O" notation is that it's common to write $a(n) = O(n^2)$ when strictly it is more accurate to say that $a(n) \in O(n^2)$ (since $O(n^2)$ is a set, and $a(n)$ is an element of that set). Then since $O(n^2) \subset O(n^4)$ (as sets), it is trivially true that if $a(n)\in O(n^2)$ then also $a(n) \in O(n^4)$. –  Chris Taylor Feb 4 '13 at 17:46
    
@ChrisTaylor: That's one way of formalizing the meaning of the big-O notation, but not the only one. See here where I propose a more intuitive (but mostly equivalent) formalization of equalities involving big-O. –  Henning Makholm Feb 4 '13 at 20:00
    
how " a∈O(x2) as x→0 " is right? is there a use to the big oh when x → 0 ? –  goon Feb 4 '13 at 21:49
    
does what Steven Stadnicki saying has the same logic as when a∈O(x^4) as x→∞ does not imply that a∈O(x^2) then! –  goon Feb 4 '13 at 21:52
show 1 more comment

1 Answer

up vote 1 down vote accepted

Yes, you can say either of those. They don't tell you as much about $a(N)$ as $a(N)=\mathcal O(N^2)$ does, but what little they do say is true.

share|improve this answer
add comment

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.