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

Improve this question
$\endgroup$
4
  • $\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, 2018 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, 2018 at 0:06
  • $\begingroup$ If $x$ goes to $\infty$, $f(x)$ goes to 0. It is better to talk about $\frac1{f(x)}$ $\endgroup$
    – John L.
    Nov 30, 2018 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, 2018 at 7:14

1 Answer 1

Reset to default
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.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.