patternMinor
The role of asymptotic notation in $e^x=1++Θ(^2)$?
Viewed 0 times
rolethenotationasymptotic
Problem
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.
$\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.
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.
- Why do they use $Θ$ here and why do they use $=$ sign?
- 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 $?
- 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.
Solution
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)$.
In contrast, here is the same plot for $10 \leq x \leq 20$. You can see that the ratio shoots up to infinity.
Credit: plots executed using Desmos.
$$
|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)$.
In contrast, here is the same plot for $10 \leq x \leq 20$. You can see that the ratio shoots up to infinity.
Credit: plots executed using Desmos.
Context
StackExchange Computer Science Q#111477, answer score: 5
Revisions (0)
No revisions yet.