# What does it mean for a function to be part of a set in O-notation?

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.

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

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.