A brief question about big-O notation

  • Thread starter Santa1
  • Start date
  • Tags
    Notation
In summary, the conversation discusses the validity of the statement that for a function f from real numbers to real numbers, if f(x) is always greater than or equal to 0 for all x, then the sum of f from a to b is equivalent to the integral of f from a to b. The conversation also includes a counterexample and a discussion of the conditions needed for the statement to hold.
  • #1
Santa1
111
0
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)
 
Mathematics news on Phys.org
  • #2
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.
 
  • #3
ok for all x in R f(x)>0 and f is continuous.
 
  • #4
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.
 
  • #5
CRGreathouse said:
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:
  • #6
mathman said:
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.
 
  • #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:
  • #8
*-<|:-D=<-< said:
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.
 
  • #9
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.
 
  • #10
arildno said:
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.
 

1. What is big-O notation?

Big-O notation is a mathematical notation used to describe the limiting behavior of a function as its input size approaches infinity. It is commonly used in computer science to analyze the performance and efficiency of algorithms.

2. Why is big-O notation important in computer science?

Big-O notation allows us to compare the time and space complexities of different algorithms and determine which one is more efficient. This is crucial in designing and implementing efficient software and systems.

3. How is big-O notation calculated?

Big-O notation is calculated by looking at the dominant term of a function as its input size approaches infinity. The order of this dominant term is then used as the big-O complexity of the function.

4. What is the difference between big-O, big-Omega, and big-Theta notation?

Big-O notation represents the upper bound of a function's growth rate, while big-Omega notation represents the lower bound. Big-Theta notation represents both the upper and lower bounds, providing a tighter bound on a function's growth rate.

5. Can big-O notation be used for non-asymptotic analysis?

Yes, big-O notation can also be used for non-asymptotic analysis, where the input size is finite. In this case, it represents the exact time or space complexity of an algorithm for a given input size.

Similar threads

  • General Math
Replies
23
Views
5K
Replies
13
Views
930
  • Calculus
Replies
1
Views
696
  • Calculus and Beyond Homework Help
Replies
3
Views
1K
  • Set Theory, Logic, Probability, Statistics
Replies
9
Views
2K
  • Math Proof Training and Practice
Replies
10
Views
1K
Replies
2
Views
1K
  • General Math
Replies
0
Views
798
Replies
6
Views
948
  • Set Theory, Logic, Probability, Statistics
Replies
7
Views
1K
Back
Top