2

Is $\sqrt{2/(27\pi n)}\sim n^{-1/2}$?

Since $$ \sqrt{\frac{2}{27\pi n}}=\sqrt{\frac{2}{27\pi}}\cdot\frac{1}{\sqrt{n}}\sim\frac{1}{\sqrt{n}}=n^{-1/2}, $$ I would say, yes, of course.

Salamo
  • 1,094

1 Answers1

9

It depends on how you define the relation $\sim$. It is certainly the case that $\sqrt{2/(27\pi n)} = \Theta(n^{-1/2})$.

But if you define $f\sim g$ to mean that $f(n)/g(n)\to 1$ as $n\to\infty$, which is how $\sim$ is usually defined, then it is not true as the limit of the quotient of $\sqrt{2/(27\pi n)}$ and $n^{-1/2}$ in your case above is not $1$.

See Asymptotic Notation.

user12344567
  • 775
  • With $\sqrt{2/(27\pi n)}=\Theta(n^{-1/2})$ you mean that $\sqrt{2/(27\pi n)}$ is of smaller or of the same order as $n^{-1/2}$ (big O-notation)? – Salamo Jun 26 '15 at 10:11
  • 2
    Yes. More precisely, by $f=\Theta(g)$ I mean that for all $n\ge n_0$ for some $n_0$ I can sandwich $f(n)$ between $C_1 g(n)$ and $C_2 g(n)$ for two absolute positive constants $C_1$ and $C_2$. Formally this means that there exists an $n_0\in\mathbb{N}$ such that there exist $C_1,C_2>0$ such that for all $n\ge n_0$ we have $C_1g(n)\le f(n)\le C_2g(n)$. It is also equivalent to saying that $f=O(g)$ and $f=\Omega(g)$. – user12344567 Jun 26 '15 at 10:15
  • If I have $f(n)\in\mathcal{O}(n^{-1/2})$ as $n\to\infty$ and $g(n)\in o(n^{-1/2})$ as $n\to\infty$, and then consider $f(n)-g(n)$ can I then neglect $g(n)$ as $n\to\infty$? – Salamo Jun 26 '15 at 10:17
  • 1
    Asymptotically you will have $f-g \in O(n^{-1/2})$. Is that what you meant? – user12344567 Jun 26 '15 at 10:19
  • I have $h(n)=f(n)-g(n)$ and I know that $f(n)\sim\sqrt{2/(27\pi n)}$ and $g(n)\in o(n^{-1/2})$. I do not see why from this it follows that $h(n)\sim\sqrt{2/(27\pi n)}$. – Salamo Jun 26 '15 at 10:23
  • 2
    Write it out: $\lim_{n\to\infty}\frac{h(n)}{\sqrt{2/(27\pi n)}} = \lim_{n\to\infty}\frac{f(n)-g(n)}{\sqrt{2/(27\pi n)}} = \lim_{n\to\infty}(\frac{f(n)}{\sqrt{2/(27\pi n)}}-\frac{g(n)}{\sqrt{2/(27\pi n)}})=\lim_{n\to\infty}\frac{f(n)}{\sqrt{2/(27\pi n)}}-0=1-0=1$, thus $h\sim\sqrt{2/(27\pi n)}$. (The limits are $1$ and $0$ because $f\sim \sqrt{2/(27\pi n)}$ and $f=o(n^{-1/2})$. – user12344567 Jun 26 '15 at 10:26
  • Ah, ok. The only thing thats now unclear to me is, why $\lim_{n\to\infty}\frac{g(n)}{\sqrt{2/(27\pi n)}}=0$. – Salamo Jun 26 '15 at 10:27
  • 1
    Because $\sqrt{2/(27\pi n)}=\Theta(n^{-1/2})$ and $g=o(n^{-1/2})$. – user12344567 Jun 26 '15 at 10:29
  • 2
    Thank you. Now I understood. You helped me a lot, thanks. – Salamo Jun 26 '15 at 10:33