Big O notation question: $\exp(-\frac{x^2}{2} + x) = O(\exp(-\frac{x^2}{2}))$ true?

Question

From the definition of the big O notation, since $-\frac{x^2}{2} + x < -(1-\epsilon)\frac{x^2}{2}$ for large $x$ and for any positive $\epsilon > 0$, I think $\exp(-\frac{x^2}{2} + x) = O(\exp(-(1-\epsilon)\frac{x^2}{2}))$ is valid. My question is whether the constant $\epsilon$ can be ommitted from the expression.

I also wonder if the denominator 2 can be ommitted.

Thank you in advance!

Answer 1

The root cause of the error made by the OP is that you cannot "apply the same operation" on both sides of a true big-O equation and assume to get a new true big-O equation in all cases.

For example, when considering $x \to +\infty$, we have

$$ x = O\left(\frac{x}3\right).$$

This can be easily verifed by noticing that for example $x < 4\cdot \frac{x}3$ for all positive $x$.

But putting both sides "to the power of $e$" yields

$$e^x = O (e^\frac{x}3),$$

which is not true:

$$e^x = e^\frac{2x}3\cdot e^\frac{x}3,$$

and $e^\frac{2x}3$, the quotient between $e^x$ and $e^\frac{x}3$, grows without bounds.

Using big-O equations is neat, but can be misleading! A term like $O\left(\frac{x}3\right)$ is not a single function, but instead a whole set of functions, where $f(x)=x$ is one of them. So writing

$$x \in O\left(\frac{x}3\right)$$

is preferred by some, because it prevents people from automatically applying techniques they know work for actual equations (like "taking both sides to the power of $e$") in this case where they don't (always) work.

Answer 2

No. When you divide $\exp(-\frac{x^2}{2} + x)$ by $\exp(-\frac{x^2}{2}))$ you get $\exp (x)$ which is not bounded.

Same thing happens if you replace $\frac {x^{2}} 2$ by $x^{2}$.