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.

I'm trying to understand the concepts underlying the O-notation.

The formal definition is:

$ O(g(n)) = \{ f(n) \textrm{ such that there exist positive constants }c\textrm{ and }n_{0} \textrm{ such that }0 \leq f(n) \leq cg(n) \} $

Then there is this notion of $f(n) = O(g(n))$ meaning $f(n) \in O(g(n))$.

What I don't understand is the reason why we use this set notation. I'm not sure to understand the actual content of this set $O(n)$.

Thanks for your help! I can be more precise if you want.

share|improve this question
2  
1. This defines $O$ (and not $\Theta$). 2. The condition to belong to $O(g(n))$ is that $|f(n)|\leqslant C|g(n)|$ for every $n\geqslant n_0$ (note the absolute value signs). –  Did Feb 9 '12 at 16:39
1  
Thank about $\Theta(n^2)$. Does it describe only $n^2$? It describes a family of functions that asymptotically (i.e., for $n \ge n_0$) behave like $n^2$. How can you represent a family of functions? Using a set. $f(n) = O(g(n))$ is an abuse of the notation: $f(n) \in O(g(n))$. –  user2468 Feb 9 '12 at 17:08
    
Sorry, I begun with $\Theta$ and then thought it would be simpler with $O$. My mistake. –  charlax Feb 9 '12 at 18:50
    
I can say that this "abuse" of notation is most annoying and is probably the main source of confusion surrounding the o-O concepts and notation. I don't understand why texts must confuse this point; it takes no more space and scant additional effort to correctly write $\in$ than it does to abusively write "=" –  ItsNotObvious Feb 9 '12 at 19:04
add comment

1 Answer 1

You use the set notation because $O(g(n))$ is actually a collection of functions (the functions that are bounded above by a constant multiple of $g(n)$), and the informal notation $f(n)=O(g(n))$ actually means $f$ is a member of a particular set.

A set of functions is, in principle, no different to any other kind of set. In most cases, it will be an infinite set, but that doesn't stop it from being a perfectly well-defined and sensible set.

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.