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

A brief question about big-O notation

  1. Apr 25, 2008 #1
    I'm sorry if this question is retarded-like but is it true that;

    [tex]f:\mathbb{R} \to \mathbb{R}, \forall x \in \mathbb{R}, f(x)\geq 0 \Rightarrow \sum_{n=a}^b f(n) = O\left(\int_a^b f(x) \mathrm{d} x\right)[/tex]

    ?

    My intuition says yes, however my mind is a tad clouded now and perhaps a short counterexample (excluding f(x)=0 please :P, edit: however if you insist i can remove the equality part of the "less than or equal") can be exhibited?

    (also sorry for bad notation and/or english)
     
  2. jcsd
  3. Apr 25, 2008 #2

    mathman

    User Avatar
    Science Advisor
    Gold Member

    I believe you would need to impose some "niceness" condition on f(x).

    Bad example: f(x)=1 for x integer, f(x)=0 otherwise.
     
  4. Apr 25, 2008 #3
    ok for all x in R f(x)>0 and f is continuous.
     
  5. Apr 25, 2008 #4

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    Let [itex]n=\lfloor x\rfloor,e=x-n[/itex] and [itex]f(x)=\max(1/n-e,0).[/itex] The integral from 1 to infinity should converge to something like [itex]\zeta(2)/2[/itex] while the sum is the harmonic series.
     
  6. Apr 26, 2008 #5

    mathman

    User Avatar
    Science Advisor
    Gold Member

    This function is not continuous. f(n)=1/n for integers. f(n-u)=0 for small u.

    However the idea can be fixed by local mirroring around each integer.
     
    Last edited: Apr 26, 2008
  7. Apr 26, 2008 #6

    CRGreathouse

    User Avatar
    Science Advisor
    Homework Helper

    That's what I was imagining, but I lost it when formalizing it for the post. Thanks for pointing that out.
     
  8. Apr 27, 2008 #7
    so the function you are speaking of is

    [tex]f(x)=\max(\frac{1}{x}-\{x\},0)[/tex]

    (where {x} denotes the fractional part of x)

    ?

    mirroring around the integers would create a continuous function, i agree. but again at a loss of some generality what if f(x) > 0 ?

    edit: perhaps [tex]f(x)=\max(\frac{1}{x}-\{x\},c)[/tex] for some small c mirrored around the integers.

    thank you for all your help!
     
    Last edited: Apr 27, 2008
  9. Apr 27, 2008 #8

    arildno

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    Dearly Missed

    Mere nonsense. you need to specify what quantity is taken to some limit, since only related to such a limiting process is the "big O" a meaningful behavioural characteristic.
     
  10. Apr 27, 2008 #9

    mathman

    User Avatar
    Science Advisor
    Gold Member

    I suspect that the only way that uou can get the big O notation condition you want is to have f(x) be monotone (for all x>y f(x)>=f(y) or for all x>y f(x)<=f(y)), and some reasonable boundedness condition.
     
  11. Apr 27, 2008 #10
    You are absolutely right, for a,b fixed the relation is between two constants. For a,b fixed I suppose you have to get another variable in there f(x,y) so that you get [tex]\sum_{n=a}^b f(n,y) \text{ and } \int_a^b f(x,y) \mathrm{d}x[/tex] for the expression to "make sense". However the idea was having the big O relation between perhaps a fixed a and variable b or vice-versa e.g. letting F(b) be the sum and G(b) the integral in the big O. (I do however apologise for the really bad setup in my original post.)

    @mathman

    Yes you seem to be right, it follows trivially if f is increasing but I'm not sure for when it decreases.

    Again, thanks for all your help.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?



Similar Discussions: A brief question about big-O notation
  1. Big-O notation (Replies: 3)

Loading...