# Is this a valid use of big-O notation?

Suppose that $$m=O(n^{c+1/2})$$ for some real $$c>0$$ and $$x=O(\sqrt{\log m})$$. Are the following two computations valid? I understand that I'm abusing notations a bit to get at the desired results.

Computation 1 \begin{align} f(x)\leq \exp(-x^2/2)&=\exp(-O(\log m))\\ &=\exp(-O(\log O(n^{c+1/2})))\\ &=\exp(-O(\log n^{c+1/2}))\\ &\leq \exp(-K_1\log n^{c+1/2})))\\ &=n^{-O(1)} \end{align} where $$K_1>0$$ when $$n$$ is sufficiently large (i.e. there exists $$K_1>0$$, $$n_0$$ such that when $$n\geq n_0$$, $$\exp(-O(\log n^{c+1/2}))\leq \exp(-K_1\log n^{c+1/2})))$$. The last quantity $$n^{-O(1)}$$ represents the set of polynomially-bounded functions (see accepted answer in this post).

Computation 2 $$f(x)\frac{m}{n^{1/2}} \leq n^{-O(1)}\frac{m}{n^{1/2}}=\leq n^{-O(1)}\frac{m}{n^{c+1/2-c}}=O(1)??$$

• Using big O notation within equations is IMHO, if not terribly sloppy, simply abhorrent mathematics. When you have set $f \in O(g)$, then pick some constant $c$ and write thereafter $f(n) \le c g(n)$ (along with a remark in the lines of "for almost all $n$"). Commented Nov 29, 2018 at 19:23
• @dkaeae Sorry but expressions such as "$f(x) = (1+o(1))\sqrt{x}$" or "$f(x)=n\log n + O(n)$" are extremely common and a lot of mathematics would get very tedious if all of those were rewritten as "$f(x) =(1+g(x))\sqrt{x}$ for some function $g\in o(1)$" and so on. Commented Nov 30, 2018 at 0:06
• If $x$ goes to $\infty$, $f(x)$ goes to 0. It is better to talk about $\frac1{f(x)}$ Commented Nov 30, 2018 at 2:00
• @David Richerby Yes, I'm aware it is usual practice, but taking those and reformulating them further to something like $\exp(-O(\log(O(n^\dots))))$ just takes things to a whole other level... Commented Nov 30, 2018 at 7:14

$$\exp(-x^2/2)\leq \exp\left(-K_1\log n^{c+1/2\,}\right), \text{ where } K_1>0$$
This is wrong. The direction of inequality should be switched. For example, let $$n\to\infty$$ and $$x$$ be constant 1, the left hand side remains a constant while the right hand side goes to 0. This error means "Computation 2" is wrong from the start.
The last quantity $$n^{-O(1)}$$ represents the set of polynomially-bounded functions.
Instead of $$n^{-O(1)}\,$$, $$n^{O(1)}$$ represents asymptotically the set of polynomially-bounded functions.