1
$\begingroup$

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.

  • 0
    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 "="2012-02-09

1 Answers 1

3

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.