# A brief question about big-O notation

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.

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

CRGreathouse
Homework Helper
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.

Last edited:
CRGreathouse
Homework Helper
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.

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!

Last edited:
arildno
Homework Helper
Gold Member
Dearly Missed
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.

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.