# Big Oh notation (Landau symbols)

1. Apr 7, 2007

### Edgardo

I have a question with respect to the Big Oh notation, in which the Landau symbol $$O(n)$$ is involved.
The Landau symbol $O(n)$ is defined as:

$$f(n)=O(g(n))$$ if there exists an integer $$n_0$$ and a constant $$C>0$$
such that for all integers $$n \geq n_0$$, $$f(n) \leq C \cdot g(n)$$.

For example $$f(n)= 5 \cdot n = O(n)$$.
Now the equality sign is not to be understand as an equality sign in the common sense, but rather as $$f(n) \in O(n)$$, see Big Oh Fallacies and Pitfalls and
the Wikipedia article.

( $5 \cdot n = O(n)$ and $2 \cdot n = O(n)$, but $5 \cdot n \neq 2 \cdot n$)

So it would be better to think of $$O(n)$$ as a set of functions.

My question:
Does anyone know why it became common to use the notation f(n)=O(g(n))?
I remember my professor mentioning that physicists introduced this sloppy notation.

Last edited: Apr 7, 2007
2. Apr 7, 2007

### Gib Z

Yes usually I use ~ notation. But I have no idea why anyone introduced that notation, I HATE it.

3. Apr 7, 2007

### quasar987

Well, Landau was a physicist, but I didn't know it was him who introduced the notation.

Certainly, if we write $f(x)=O(g(x))$, we mean that f belongs to the class of function for which there exists a C with $$f(x) \leq C \cdot g(x)$$ for some x_0 onward. So yes, IMHO, writing $f(x)\in O(g(x))$ would be more accurate, but it would not make sense to write things like

$$f(x)=\sum_{k=0}^{n-1}\frac{f^{(k)}(0)}{k!}x^k+O(x^n)$$

We would have to write

$$f(x)=\sum_{k=0}^{n-1}\frac{f^{(k)}(0)}{k!}x^k+g(x) \ \ \ \ \ \ \ \mbox{where} \ g(x)\in O(x^n)$$

There is no ambiguity in the first formula. It reads "f(x)=sum plus some function for which there exists a C with $$f(x) \leq C \cdot g(x)$$ for some x_0 onward". In the second, we gain in rigor but loose a little bit of gut feeling for the equation. Personally, I'm fine with the original notation.

Last edited: Apr 7, 2007
4. Apr 7, 2007

### Crosson

I write, for example:

$$O( ln(n^2)) = O(ln (n))$$

and I never thought to write:

$$ln( n^2) = O(ln(n))$$

I liked quasar's post, and I agree with the conclusion that the gain in rigor is not worth the extra effort. Compare with the hyper-common:

"A topological space is a pair $$(X,\tau)$$ satisfying...

...now let $$X$$ be a topological space..."

5. Apr 7, 2007

### Data

Well, there's nothing wrong with that quite yet!

6. Apr 7, 2007

### arildno

Well, is this overload of the equality sign any more grievous than the programmers' assignment operation i=i+1?