Examples of such use of Big O notation can be found for instance on Wolfram Alpha here. More details on the Wikipedia page.

The idea, as I understand it, is that the term between parenthesis in Big O bounds the rest of the series asymptotically (as $x$ goes to $0$ or $\infty$) giving and elegant way of writing the series (if you don't like "+ ..." or "etc") while also providing an error approximation. Taking the example of $e^x$:

$$ e^x=1+x+\frac{x^2}{2!}+\frac{x^3}{3!}+\frac{x^4}{4!}+O(x^5) $$

When we write $O(x^5)$ we mean that all the rest of the terms (like $\frac{x^6}{6!}+\frac{(x^7)}{7!}+\frac{x^8}{8!}+\cdots+\frac{x^y}{y!}$) are bounded by $x^5$ as $x$ goes to $0$. Giving a more concrete example if we take $e^{2.42}$ then this is more or less $1 + 2.42 + (\frac12)(2.42)^2 + (\frac16)(2.42)^3 + (\frac{1}{24})(2.42)^4$ and the error between the approximation and the actual value is no larger than $2.42^5$.

The question is how do we know this?

Certainly $x^5$ bounds, as $x$ goes to $0$, each term individually ($Cx^n=O(x^5)$ as $\lim_{x\to\infty}$ as long as $n>5, C$ constant) but how do we prove the sum of all the individual terms is bounded? We have to show that:

$$ O(x^5)=\frac{x^6}{6!}+\frac{x^7}{7!}+\frac{x^8}{8!}+\frac{x^9}{9!}+\frac{x^{10}}{10!}+\frac{x^{11}}{11!}+...),x\rightarrow 0 $$

Falling back on the previous example, maybe the infinite sum will actually be slightly larger than $2.42^5$. How do we prove this is actually not the case? While I have used the example of $e^x$, feel free to give a more general proof, and not one for this particular function only.

Your help with this issue will be greatly appreciated.

Thank you for taking the time to read this and have a good day.

Note: I wrongly asked this on Math Overflow and copied it here. I'm not sure whether the other question gets transferred or if I made the right choice in reasking here.

  • 2
    $\begingroup$ $u(x)=O(x^5)$ does not mean $|u(x)|\leqslant |x|^5$ but $|u(x)|\leqslant C|x|^5$ for some finite $C$, for every $x$ in a neighborhood of $0$. As is explained on the WP page you link to. $\endgroup$ – Did Apr 10 '14 at 19:12
  • 2
    $\begingroup$ It sounds like what you're after is the Taylor series with remainder term; does en.wikipedia.org/wiki/… answer any of your questions? $\endgroup$ – Steven Stadnicki Apr 10 '14 at 19:13
  • $\begingroup$ @Did My bad... in light of this the answer doesn't seem that complicated anymore. Thank you. $\endgroup$ – Zav Apr 10 '14 at 20:23

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.