Big-O notation -- is it mainly used to classify rate of growth or rate of decay to zero?

Question

For example, $e^{x} = 1 + x + x^2/2 + O(x^3)$,

and we interpret $O(x^3)$ as the remainder term that goes to zero like $x^3$.

What's the primary usage of Big-O notation? (strictly in math classes, e.g., real (complex) analysis I/II and not in computer science.)

Basically, I am a little shaky about using Big-O notation to classify rates of growth (to infinity) but am more comfortable using it to classify rates of decay (to zero), say, of a remainder term of a Taylor / Laurent expansion.

Edit: My main confusion is this: the remainder term in the example I gave decays to zero like x^3, hence it's in O(x^3), but the remainder obviously does not grow like x^3, as x goes to infinity -- which means the remainder is not in O(x^3)...?

Thanks,

Answer 1

Part of what is probably confusing you is that big/little oh notation get used with different limits in different contexts, and we quite frequently don't say what the limit actually is explicitly. For instance, in the context of Taylor's theorem, $e^x=1+O(x)$ is a statement about the behavior of $e^x$ near zero, not about its behavior elsewhere. On the other hand, $n^2+n+1=O(n^2)$ is a statement about a limit as $n \to \infty$. In principle you could even have a limit as a variable tends to some nonzero finite value. We can explicitly say what the limit is, by writing things like "$e^x=1+O(x)$ as $x \to 0$", but more often than not we don't do this, because the notation is meant as a shorthand anyway.

Regardless of what sort of limit we are dealing with, big Oh notation really is not about growth or about decay, it is about boundedness. For instance $e^x=1+O(x)$ means that $\frac{e^x-1}{x}$ is a bounded function near zero; $n^2+n+1=O(n^2)$ means that $\frac{n^2+n+1}{n^2}$ is bounded for large $n$. These boundedness properties tell us something about growth or decay of the original function, but only because we know whether the function we are comparing to is growing or decaying in the relevant limit.

Answer 2

Could be either. Suppose $f(x)=O(g(x))$as $x\to\infty$.

If $g(x)\to\infty$ as $x\to\infty$, then we have an estimate of the growth rate.

If $g(x)\to 0$ as $x\to\infty$, then it is an estimate of decay.

Answer 3

The idea is that you approximate some function or series by something that is simpler or better understood, and then use plus some other more complicated thing, the $O(x)$, to give the true function or series. If you use it correctly the values of $O(x)$ are very small or zero in the areas of the function or series that you are interested in studying and can then be approximated by whatever is similar to the.

The reason you appear to be confused is that for taylor expansions the big-O notation $O(x)$ requires infinite terms to give the true finite value of the function you are trying to approximate, when you take more of the components of the $O(x)$ and place them into the function you are using to approximate the big-O gets smaller until you consider the whole taylor expansion when $O(x)$ becomes zero once all of its terms have been removed.

for instance you could take you function $e^x=1+x+x^2/2+O(x^3)$ and include the $x^2/2$ in the $O(x)$ to reduce accuracy but make computation easier. this increases the terms in $O(x)$, but reduces the accuracy of the approximation.

you could also add one extra term into your taylor series to get $e^x=1+x+x^2/2+x^3/6+O(x^4)$ to reduce the number of terms in your approximation, but also increase the difficulty in calculating you approximation.

I hope this explanation of the logic behind why it works made sense.

Answer 4

Big-O, little-o are just notational shortcuts for the follwing:

$f$ is "big-O" $g$ if and only if there is an $M> 0$ such that

$\left | f(x) \right |\leq M\left | g(x) \right |$ for all $x$ greater than some fixed $x_{0}$.

$f$ is "little-o $g$" means that for all $\epsilon >0$, there is an $x_{0}$ for which

$\left | f(x) \right |\leq \epsilon \left | g(x) \right |$ for $x\geq x_{0}$

So big-O says the growth of $f$ is bounded by that of $g$--i.e. $f$ behaves like $g$ as $x$ grows without bound-- while little-O says the when $f$ is divided by $g$, the limit $x\rightarrow \infty $ is 0.

Notice f little-0 g implies f big-O g but not conversely.