3
$\begingroup$

I'm reading CLRS and there is the following:

When x→0, the approximation of $e^x$ by $1+x$ is quite good: $$e^x=1+𝑥+Θ(𝑥^2)$$

I suppose I understand what means this equation from math perspective and, also, there is an answer in another cs question. But I don't understand some things, so have a few questions.

  1. Why do they use $Θ$ here and why do they use $=$ sign?
  2. Is it possible to explain how the notation here is related to the author's conclusion that $e^x$ is very close to $1 + x$ when $x \rightarrow 0 $?
  3. Also, how is it important here that $x$ tends to $0$ rather than to $\infty$ as we usually use asymptotic notations?

I'm sorry if there are a lot of questions and if they are stupid, I'm just trying to master this topic.

$\endgroup$
  • 1
    $\begingroup$ Note that the quoted paragraph continues: "In this equation, the asymptotic notation is used to describe the limiting behavior as $x\to 0$ rather than as $x\to \infty$". The way $\Theta$ is used here is completely different from how it is used anywhere else in the book. $\endgroup$ – Tom van der Zanden Jul 4 at 8:26
4
$\begingroup$

What the equation means is that there exist constant $A>0$ and $B,C$ such that $$ |x| \leq A \Longrightarrow Bx^2 \leq e^x-1-x \leq Cx^2. $$ In particular, for small $x$, $e^x$ is very close to $1+x$, since the error is only $O(x^2)$ (when $x$ is small, $x^2$ is much smaller than $x$).

The same estimate doesn't hold for large $x$ — indeed, $e^x$ grows faster than $x^2$, indeed faster than any fixed power of $x$. So the quoted estimate only holds for small $x$.


Here is a graphic example. Below is the plot of $\frac{e^x-1-x}{x^2}$ for $|x| \leq 0.1$. You can see that it is very close to $0.5$. This is consistent with the Taylor expansion of $e^x$, which is $1 + x + x^2/2 + O(x^3)$.

enter image description here

In contrast, here is the same plot for $10 \leq x \leq 20$. You can see that the ratio shoots up to infinity.

enter image description here

Credit: plots executed using Desmos.

$\endgroup$
  • $\begingroup$ I think I got it. Thank you very much for your detailed answer :) $\endgroup$ – E. Shcherbo Jul 5 at 20:05

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.