0
$\begingroup$

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)?? $$

$\endgroup$
  • $\begingroup$ 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$"). $\endgroup$ – dkaeae Nov 29 '18 at 19:23
  • 1
    $\begingroup$ @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. $\endgroup$ – David Richerby Nov 30 '18 at 0:06
  • $\begingroup$ If $x$ goes to $\infty$, $f(x)$ goes to 0. It is better to talk about $\frac1{f(x)}$ $\endgroup$ – Apass.Jack Nov 30 '18 at 2:00
  • $\begingroup$ @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... $\endgroup$ – dkaeae Nov 30 '18 at 7:14
1
$\begingroup$

If these computations appear in a paper for me to review, I would like to ask the author to rewrite.

$$\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.

$\endgroup$

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.