A brief question about big-O notation

[Santa1]

I'm sorry if this question is retarded-like but is it true that;

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)

?

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)

 

[mathman]

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.

 

[Santa1]

ok for all x in R f(x)>0 and f is continuous.

 

[CRGreathouse]

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

 

[mathman]

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

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.

 

[CRGreathouse]

However the idea can be fixed by local mirroring around each integer.

That's what I was imagining, but I lost it when formalizing it for the post. Thanks for pointing that out.

 

[Santa1]

so the function you are speaking of is

f(x)=\max(\frac{1}{x}-\{x\},0)

(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 f(x)=\max(\frac{1}{x}-\{x\},c) for some small c mirrored around the integers.

thank you for all your help!

 

[arildno]

I'm sorry if this question is retarded-like but is it true that;

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)

?

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)

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.

 

[mathman]

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.

 

[Santa1]

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.

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 \sum_{n=a}^b f(n,y) \text{ and } \int_a^b f(x,y) \mathrm{d}x 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.