A brief question about big-O notation

  • Thread starter Santa1
  • Start date
107
0

Main Question or Discussion Point

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)
 

Answers and Replies

mathman
Science Advisor
7,713
397
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.
 
107
0
ok for all x in R f(x)>0 and f is continuous.
 
CRGreathouse
Science Advisor
Homework Helper
2,817
0
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.
 
mathman
Science Advisor
7,713
397
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.
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
Science Advisor
Homework Helper
2,817
0
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.
 
107
0
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:
arildno
Science Advisor
Homework Helper
Gold Member
Dearly Missed
9,946
130
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)
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
Science Advisor
7,713
397
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.
 
107
0
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 [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.
 

Related Threads for: A brief question about big-O notation

  • Last Post
Replies
2
Views
2K
  • Last Post
Replies
3
Views
2K
Replies
4
Views
6K
  • Last Post
Replies
3
Views
1K
Replies
23
Views
1K
  • Last Post
Replies
2
Views
578
  • Last Post
Replies
2
Views
1K
Replies
1
Views
1K
Top