Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Big Oh notation (Landau symbols)

  1. Apr 7, 2007 #1
    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: Apr 7, 2007
  2. jcsd
  3. Apr 7, 2007 #2

    Gib Z

    User Avatar
    Homework Helper

    Yes usually I use ~ notation. But I have no idea why anyone introduced that notation, I HATE it.
     
  4. Apr 7, 2007 #3

    quasar987

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    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: Apr 7, 2007
  5. Apr 7, 2007 #4
    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..."
     
  6. Apr 7, 2007 #5
    Well, there's nothing wrong with that quite yet! :wink:
     
  7. Apr 7, 2007 #6

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Well, is this overload of the equality sign any more grievous than the programmers' assignment operation i=i+1?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: Big Oh notation (Landau symbols)
  1. Big Oh notation help? (Replies: 2)

Loading...