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?