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

Homework Help: Big-O Notation

  1. May 30, 2006 #1
    [tex]\sum_{p\leq N}\frac{1}{p}=\log\log N + A + O(\frac{1}{\log N})[/tex]

    Does it mean that we can simply replace the O part with a function that is a constant times 1/(log N)? What would be the difference between [tex] A + O(\frac{1}{\log N})[/tex] and [tex]O(1)[/tex]?
  2. jcsd
  3. May 30, 2006 #2


    User Avatar
    Science Advisor
    Homework Helper

    No it doesn't. If f(n)=g(n)+O(h(n)) then there is a constant C where |f(n)-g(n)|<=C*h(n) in some suitable range of n. It does NOT mean f(n)=g(n)+C*h(n). Consider cos(x)=O(1) but we don't have cos(x)=constant.

    The first gives more information (it implies the second but not vice versa). Even if you don't know the constant A (it can be expressed in terms of an infinite sum over the primes here though) it still says something about the structure of the lower order terms.
Share this great discussion with others via Reddit, Google+, Twitter, or Facebook