Big Oh notation (Landau symbols)

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

 

[Gib Z]

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

 

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

 

[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..."

 

[Data]

I write, for example:


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

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

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

 

[arildno]

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