1
$\begingroup$

I'm wondering how to formally show that $\sqrt{n}o(\sqrt{n}) = o(n)$. The problem I'm having is that I don't really know how to formally resolve the multiplication on the LHS. It would be straightforward to show the result for $\sqrt{n}O(\sqrt{n}) = O(n)$ by simply replacing the $O(\sqrt{n})$ with $c\sqrt{n}$ for some constant $c$.

$f(n) \in o(\sqrt{n})$ only tells me that $\lim_{n\rightarrow\infty}f(n)/\sqrt{n}=0$, which doesn't seem to be very helpful here. Is there an way to treat $o(\sqrt{n})$ analogously to $O(\sqrt{n})$?

  • 3
    \begin{array}{c l} f\in \sqrt{n}o(\sqrt{n}) & \iff f/\sqrt{n}\in o(\sqrt{n}) \\ & \iff \lim_{n\to\infty}\frac{f(n)/\sqrt{n}}{\sqrt{n}}=0 \\ & \iff\lim_{n\to\infty}\frac{f(n)}{n}=0 \\ & \iff f\in o(n). \end{array}2012-07-17

2 Answers 2

2

Suppose $f(n)\in o(\sqrt{n})$. We want to show $\sqrt{n}f(n)\in o(n)$, i.e. that $\lim\limits_{n\to\infty} \sqrt{n}f(n)/n=0$. All we need to do is observe that $\sqrt{n}f(n)/n=f(n)/\sqrt{n}$ and we're done.

3

Suppose $b_n=o(\sqrt{n})$. Then $\lim_{n\to\infty} \frac{\sqrt{n}b_n}{n}=\lim_{n\to\infty} \frac{b_n}{\sqrt{n}}=0$ by definition of "$o$-little". So $\sqrt{n}$ times something that is $o(\sqrt{n})$ gives you something that is $o(n)$. That's what your equality means.