1. Limited time only! Sign up for a free 30min personal tutor trial with Chegg Tutors
    Dismiss Notice
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




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

Loading...