4
$\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 '19 at 8:26
5
$\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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ I think I got it. Thank you very much for your detailed answer :) $\endgroup$ – E. Shcherbo Jul 5 '19 at 20:05
  • $\begingroup$ @YuvalFilmus I found you answer great.. Now I felt like clarifying a few points, (1) the authors have used the asymptotic notation in a completely different meaning instead of $n\geq n_0$ they have changed the definition to $n\leq\epsilon$ where $\epsilon$ is a small positive quantity. (2) assuming (1) and as you showed $e^x-x-1$ is tight bounded by $x^2$ for very small $x$. Is this so? $\endgroup$ – Abhishek Ghosh Jun 19 at 16:02
  • $\begingroup$ Right, usually big Theta is with respect to $n \to \infty$, here it is used for $x \to 0$. $\endgroup$ – Yuval Filmus Jun 19 at 16:48
  • $\begingroup$ Taylor's theorem shows that for any $k$, we have $e^x = 1 + x + \cdots + x^k/k! + e^{\theta x} x^{k+1}/(k+1)!$, where $\theta$ is between $0$ and $x$. $\endgroup$ – Yuval Filmus Jun 19 at 16:50

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.