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.

  • 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).2012-02-09
  • 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))$.2012-02-09
  • 0
    Sorry, I begun with $\Theta$ and then thought it would be simpler with $O$. My mistake.2012-02-09
  • 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