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

Landau Notation question

  1. Sep 6, 2009 #1
    I have a rather simple question which requires a direct answer:

    We have two functions, f(x) and g(x).

    I know that f(x) << g(x) is the same as f(x) = O(g(x)).
    But if f(x) >> g(x), how can I write f(x) in terms of g(x) using the one of the four Landau symbols ([tex]\Omega[/tex], [tex]\omega[/tex], o, or O)?

    I suspect that f(x) >> g(x) means the same as f(x) = o(g(x)), but I am not sure.
  2. jcsd
  3. Sep 6, 2009 #2
    f(x) >> g(x) translates as:
    [tex]f(x) = \Omega(g(x))[/tex].
    Although according to Knuth, using an equality in front of a Landau symbol is supposedly abuse of notation (apparently [tex]\in[/tex] is preferred).
    Last edited: Sep 6, 2009
  4. Sep 7, 2009 #3
    Actually, I would say o not O for this.

    log n << n means log n is MUCH SMALLER than n, not allowed to be comparable to n.
  5. Sep 7, 2009 #4
    No, it's O. Look up "Vinogradov symbol" and you'll see that I am right.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook