1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Big O notation

  1. Jul 28, 2007 #1
    1. The problem statement, all variables and given/known data
    Can someone explain big O notation to me in the context of taylor series?

    For instance, how do you know that

    sint t = t - t^3/(3t)! + O(t^5) as t -> 0?

    Does that hold when t -> infinity as well?

    Is there a generalization of this rule? Is it derived from the formula for the remainder of a taylor series?

    2. Relevant equations

    3. The attempt at a solution
  2. jcsd
  3. Jul 28, 2007 #2


    User Avatar
    Homework Helper

    loosely, [tex]O(t^n)[/tex] means terms of the order of [tex]t^n[/tex] or above. in other words it is used to represent higher order terms that are usually not so important compare to other terms in the series when you are taking some limit. But precisely, it tells you how "fast" such terms are approaching the limit (whether it is zero or not). there are also symbols like [tex]\Theta(t^n)[/tex] which in strict computating/information theory sense are different from [tex]O(t^n)[/tex]. It approaches the limit at different "speed". For maths/physics usage we usually do not care about such distinction or the real asymptotic behaviors. or to avoid confusion we just write in words what the behavior is like rather than relying on the usual interpretation of the symbols (which may not be universal anyway)
  4. Jul 28, 2007 #3
    I understand the definition of big O (O(f(x)) = g(x) if there is a constant C such that Cf(x) = g(x) for all x sufficiently small (or large)).

    My question was when you have a taylor series or a polynomial how do you know when you can replace a set of terms with a big O.

    So, you are saying it would not work if t approached infinity I think?
  5. Jul 28, 2007 #4


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Taylor's theorem gives you a remainder term.
  6. Jul 28, 2007 #5
    The Lagrange form of the remainder holds when t -> 0 and t -> infinity, right?

    So sin t = t - t^3/3! + O(t^5) when t-> 0 and t-> infinity, right?

    Also is it true that if f = O(t^5), then (1/t)*f = (1/t)* O(t^5) = O(t^4)?

    How would you show that?
    Last edited: Jul 28, 2007
  7. Oct 2, 2007 #6
    This notation is possibly the most confusing thing I have every encountered. I have seen it defined at least 5 different ways. Some books define it when t is sufficiently large, some books define when t is sufficiently small, some books define when t is in a range. If someone else could agree that this is confusing, I would be very happy. If someone else could explain to me which context the respective definitions are used, I would be very happy.
    For example, how do you define big O notation when you use it to truncate a taylor series? And if someone could answer the questions in my last post I would like that?
    This stuff is driving me crazy!
    Could someone show me a complete proof using the definition of big O notation and Taylor's theorem of why we can use the big O notation in Taylor expansions? That would be amazingly helpful.
    Last edited: Oct 2, 2007
  8. Oct 2, 2007 #7


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    Suppose f is differentiable n + 1 times on a closed, bounded interval I containing a in its interior. Then,

    \left| f(x) - \sum_{k = 0}^n \frac{d^k f}{dx^k}(a) \frac{(x - a)^k}{k!} \right|
    &= \left| \frac{f^{n+1}(\xi)}{(n+1)!} (x - a)^{n + 1} \right|
    &\leq \max_{t \in I} \left| \frac{f^{n+1}(t)}{(n+1)!} \right| |x - a|^{n + 1}
    \in O((x - a)^{n + 1}).
    ([itex]\xi[/itex] is an element between x and a that makes that first equality true)
    Last edited: Oct 2, 2007
  9. Oct 2, 2007 #8
    OK...you used Taylor's theorem. Now can you use the definition of big O and Taylor's theorem to verify that last inclusion? With that parenthetical, one needs to be very careful about how you define big O to make that work. That is what confuses me so much.
  10. Oct 2, 2007 #9


    User Avatar
    Science Advisor
    Homework Helper

    Big-O notation is, in many senses inconsistent notation.

    Basically, [itex]g(x)=O(n)[/itex] means
    [tex]g(x) \leq K_g x[/tex]
    on some interval (which must be inferred from context).

    Since Taylor series aren't necessarily convergent, it's not generally possible to have a bounded error term. However, in regions where the series converges, it should make sense that there would be an upper and lower bound on the trailing fraction of the sum.
  11. Oct 2, 2007 #10
    Right. I understand why Taylor's theorem works, I am just still a little confused about how big O notation works with it. So, you are saying that in the Taylor series case the O notation only works when we are in the interval -a and a? So, every book that replaces a Taylor expansion with a big O should have technically said that their equation only works between -a and a, right?
  12. Oct 2, 2007 #11

    Gib Z

    User Avatar
    Homework Helper

  13. Oct 2, 2007 #12
    Yes, I have seen little ohs, but in Taylor series truncations it is always big Oh that is used. Can someone please answer my questions in post #10?
  14. Oct 2, 2007 #13


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    My example was with an interval containing a in its interior -- not an interval about zero with radius a.

    And no, one doesn't have to qualify the big O notation -- recall that big O does not require [itex]|f(x)| < M |g(x)|[/itex] to be true everywhere. It merely has to be true for some interval about a.
  15. Oct 3, 2007 #14


    User Avatar
    Staff Emeritus
    Science Advisor

    The whole point is that
    [tex]sin(x)= x- \frac{1}{6}x^3+ \frac{1}{5!}x^5- \frac{1}{6!}x^6+ \cdot\cdot\cdot[/tex]
    so that
    [tex]sin(x)= x- \frac{1}{6}x^3+ x^5(\frac{1}{5}- \frac{1}{6!}x+ \dot\dot\cdot[/tex]
    That just says that sin(x) can be written as x- (1/6)x3 "plus other terms that involve at least the fifth power of x".

    Your confusion with intervals may be because the only time that's important is when the higher powers can be ignored. That happens for small values of x, not large ones.
  16. Oct 3, 2007 #15
    To elaborate on what HallofIvy said, there is a relationship known as the 'small angle approximation.' It is given as

    \sin{x} \simeq x

    for small x. For slightly larger values of x, you can use

    \sin{x} \simeq x - \frac{x^{3}}{3!}
    Last edited: Oct 3, 2007
  17. Oct 3, 2007 #16
    So, the definition of big Oh that is used to truncate Taylor series is:

    f(x) = O(g(x)) when there exists and interval (a,b) s.t. there exists a constant C such that abs(f(x))<K*abs(g(x)) when x is in (a,b)?

    It doesn't really seem like that is saying much since it is true for any 2 functions that intersect i.e. x = O(x^15) and x^15 = O(x) because you can just take a small interval around zero. Am I missing something?
  18. Oct 3, 2007 #17


    User Avatar
    Science Advisor
    Homework Helper

    Let's assume that [itex]x=O(x^{15})[/itex] near zero so there is some positive constant [itex]k[/itex] so that
    [tex]kx < x^{15}[/tex]
    (Where [itex]\epsilon[/itex] is some small positive number.)
    Now consider
    [tex]x=\min\left(\frac{\epsilon}{2}, \frac{\sqrt[14]{k}}{2}\right)[/tex]
    which is clearly on the interval, but which violates the inequality.
  19. Oct 3, 2007 #18


    User Avatar
    Staff Emeritus
    Science Advisor
    Gold Member

    (a, b) has to contain your target point. Maybe an additional decoration would help; the following are true:

    [tex]x \in O_{+\infty}(x^{15})[/tex]
    [tex]x^{15} \in O_0(x)[/tex]
    [tex]x^{15} \notin O_{+\infty}(x)[/tex]
    [tex]x \notin O_0(x^{15})[/tex]

    The target point is usually left out because it's clear from context. e.g. if you're analyzing algorithms, you are always looking at behavior near [itex]+\infty[/itex].
    Last edited: Oct 3, 2007
  20. Nov 1, 2007 #19
    I see. And you could also write e.g.

    [tex](x-5)^{15} \in O_5(x-5)[/tex]

    which is why it is possible to use big O notation whenever you have a finite Taylor series expansion, right?
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?

Similar Discussions: Big O notation
  1. Big-O notation (Replies: 1)

  2. Big O notation (Replies: 1)

  3. Big-O Notation (Replies: 1)