Understanding little-o notation

  • Thread starter zonk
  • Start date
  • Tags
    Notation
In summary: The vector space of all functions from the real line to the real line is denoted by L(R). The dimension of L(R) is 2.5. Functions in little-o are said to be analytic if there exists a real number h such that for all x in R, f(x)h is a real function. Functions in little-o are also said to be differentiable if there exists a real number g such that for all x in R, there exists a real number h such that f′(x)h is a real function.
  • #1
zonk
44
0
I am currently reading Apostol volume 1, and I'm having trouble understanding little-o notation. I have searched the web for free resources, but can't find any. I don't quite understand his proof for theorem 7.8.e, and I don't understand his examples.

For instance, why does [itex]\frac{1}{1 + g(x)} = 1 - g(x) + g(x)\frac{g(x)}{1 + g(x)} = 1+ g(x) + o(g(x))[/itex] as g(x) approaches 0?

Also for his example, why does [itex]o(-\frac{1}{2}x^2 + o(x^3)) = o(x^2)[/itex]?

Anyone know of any free resource that explains this lucidly?
 
Last edited:
Physics news on Phys.org
  • #2
I think I understand it better. -1/2x^2 is of order o(x^2), and since we are considering smaller orders o(x^2) + o(x^3) = o(x^2). Also the third term approaches zero and 1 - g(x) is of order o(g(x)). Is this understanding correct?
 
  • #3
No, I still don't understand little-o. I tried some exercises and failed miseraby. Is it something we need to understand a future section in Apostol, or is it something books on real analysis present and can safely be skipped with respect to understanding the rest of Apostol Calculus volume 1 and 2?
 
  • #4
zonk said:
No, I still don't understand little-o. I tried some exercises and failed miseraby. Is it something we need to understand a future section in Apostol, or is it something books on real analysis present and can safely be skipped with respect to understanding the rest of Apostol Calculus volume 1 and 2?

Just to confirm, is your little o(h(x)) defined to be lim (x->0) h(x)/x -> zero? If not what is it?
 
  • #5
Yeah, except x can approach any limit, not just 0 or infinity. So f(x) = o(g(x)) means that f(x)/g(x) -> 0.
 
  • #6
zonk said:
I am currently reading Apostol volume 1, and I'm having trouble understanding little-o notation. I have searched the web for free resources, but can't find any. I don't quite understand his proof for theorem 7.8.e, and I don't understand his examples.

For instance, why does [itex]\frac{1}{1 + g(x)} = 1 - g(x) + g(x)\frac{g(x)}{1 + g(x)} = 1+ g(x) + o(g(x))[/itex] as g(x) approaches 0?

Also for his example, why does [itex]o(-\frac{1}{2}x^2 + o(x^3)) = o(x^2)[/itex]?

Anyone know of any free resource that explains this lucidly?

You can find the rigorous definition of little-o in Section 5 of Chapter 3 from Advanced Calculus by Loomis http://www.math.harvard.edu/~shlomo/

A function [itex]f \in \mathbb{o}[/itex] if [itex]f(0)=0[/itex] and [itex]\left\|f(\alpha)\right\|/\left\| \alpha \right\| \rightarrow 0[/itex] as [itex]\alpha \rightarrow 0[/itex]

All functions in little-oh constitute a vector space
 

Related to Understanding little-o notation

1. What is little-o notation and why is it important in mathematics and computer science?

Little-o notation is a mathematical concept used to describe the behavior of a function as its input approaches a certain value. It is used to measure the rate of growth of a function and is important in mathematics and computer science because it helps analyze the efficiency and complexity of algorithms and functions.

2. How is little-o notation different from big-O notation?

While big-O notation describes the upper bound or worst-case scenario of a function, little-o notation describes the exact behavior of a function as its input approaches a certain value. This means that little-o notation is more precise and can provide more information about the behavior of a function.

3. Can you give an example of a function and its corresponding little-o notation?

A common example is the function f(x) = x^2. As x approaches infinity, the function increases at a rate that is faster than any constant multiple of x. This can be represented as little-o notation, f(x) = o(x^2).

4. How is little-o notation used in analyzing algorithms?

Little-o notation is used to measure the time complexity of algorithms. By analyzing the behavior of a function, we can determine how efficient an algorithm is and how it will perform as the input size increases. This allows us to compare and choose the most efficient algorithm for a given problem.

5. What are the limitations of using little-o notation?

One limitation is that it only describes the behavior of a function as its input approaches a certain value, so it may not accurately reflect the behavior of a function for all input values. Additionally, it does not take into account the constant factors or lower order terms that may affect the performance of an algorithm. Therefore, it should be used in conjunction with other notations, such as big-O and theta, for a more comprehensive analysis.

Similar threads

  • Calculus
Replies
6
Views
2K
Replies
1
Views
2K
Replies
36
Views
4K
Replies
1
Views
1K
Replies
2
Views
1K
Back
Top