Big Oh notation (Landau symbols)

  • Thread starter Edgardo
  • Start date
  • #1
703
13

Main Question or Discussion Point

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

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

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

( [itex]5 \cdot n = O(n)[/itex] and [itex]2 \cdot n = O(n)[/itex], but [itex] 5 \cdot n \neq 2 \cdot n[/itex])

So it would be better to think of [tex]O(n)[/tex] 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:

Answers and Replies

  • #2
Gib Z
Homework Helper
3,346
5
Yes usually I use ~ notation. But I have no idea why anyone introduced that notation, I HATE it.
 
  • #3
quasar987
Science Advisor
Homework Helper
Gold Member
4,773
8
Well, Landau was a physicist, but I didn't know it was him who introduced the notation.

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

[tex]f(x)=\sum_{k=0}^{n-1}\frac{f^{(k)}(0)}{k!}x^k+O(x^n)[/tex]

We would have to write

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

There is no ambiguity in the first formula. It reads "f(x)=sum plus some function for which there exists a C with [tex]f(x) \leq C \cdot g(x)[/tex] 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:
  • #4
1,250
2
I write, for example:

[tex] O( ln(n^2)) = O(ln (n)) [/tex]

and I never thought to write:

[tex] ln( n^2) = O(ln(n)) [/tex]

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 [tex] (X,\tau) [/tex] satisfying...

...now let [tex] X [/tex] be a topological space..."
 
  • #5
998
0
I write, for example:


"A topological space is a pair [tex] (X,\tau) [/tex] satisfying...

...now let [tex] X [/tex] be a topological space..."
Well, there's nothing wrong with that quite yet! :wink:
 
  • #6
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,970
131
Well, is this overload of the equality sign any more grievous than the programmers' assignment operation i=i+1?
 

Related Threads on Big Oh notation (Landau symbols)

  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
Replies
9
Views
3K
  • Last Post
Replies
11
Views
2K
  • Last Post
Replies
4
Views
2K
  • Last Post
Replies
1
Views
1K
  • Last Post
Replies
2
Views
1K
Top