Meaning of $ e^x = 1 + x + \Theta(x^2)$?

Question

In the CLRS book chapter 3: When $x → 0$, the approximation of $e^x$ by $1+x$ is quite good:

$$e^x = 1 + x + \Theta(x^2)$$

How is it to be interpreted, what is the role of asymptotic notation here? If I interpret the $\Theta$ naively as standard big-$O$ notation then this statement surely makes no sense?!

Answer 1

I could understand why this might be confusing and, indeed, it was when I first saw it as well. The trick is that one is probably used to "big-O" ("big-$\Omega$", "big-$\Theta$", etc.) notations as being used in phrases like "this algorithm is $O(n^2)$" and so forth which suggest that big-O describes a property of some particular object of interest, yet here it is being used as a quantity in and of itself.

However, there is no mystery to this: If you use a big-$O$ (etc.) like it's a quantity, i.e. as you give

$$1 + x + \Theta(x^2)$$

that means that it is effectively a placeholder for an unspecified function that has the indicated asymptotic behavior. In the case you give, the unspecified function is the remainder of the exponential series - the function that must be substituted in order to make the equality hold exactly. The notation tells you the behavior of that remainder as you vary $x$, and thus how the error in approximating $e^x$ by $1 + x$, varies as well. It is also important to note that big-Os have a "direction" associated with them, much like a limit: in the phrase related to the running time of a computer algorithm, the asymptotic is taken as $n$ goes to positive infinity. Here, it is (usually!) taken as $x$ goes to zero. This may be notated with something like

$$e^x = 1 + x + \Theta(x^2),\ \ \ \ \ \ x \rightarrow 0$$

but it also may not be if this is simply implied by context: in this case we pretty much know a Taylor polynomial is bad once you're suitably far out from its point of expansion, so what we'd really like to know is how good it gets, i.e. how much the error shrinks, when you get suitably close to the point of expansion, since that can tell you both if you're close enough to hit a desired level of accuracy and/or if you need to go closer.

Answer 2

The role of the asymptotic notation here is the same as the role of most asymptotic notation anywhere: To tell you how large the error is. In this case, using $\Theta$, the term tells you that the error is roughly proportional to $x^2$ (for small $x$).

There is, of course, a rigorous definition of what "roughly proportional" means in this case. It means that as long as $|x|<K$ for some bound $K$, there are two real constants $0<c<C$ such that the (absolute value of the) error of your approximation is between $cx^2$ and $Cx^2$.