I have some trouble understanding how $\mathcal{o}$-notation works. Take for example $f \in \mathcal{o}(n^{-1/2})$. Then what would the limiting behavior of $nf$ or $f^2$ be?
Can somebody explain this to me?
Asked
Active
Viewed 59 times
0
-
Welcome to math stack exchange! Is $n$ tending to $\infty$ or to $0$ ? – Peter May 05 '17 at 12:42
-
$f$ must satisfy $$\lim_{n\rightarrow \infty} f(n)\cdot \sqrt{n}=0$$ Hence $$\lim_{n\rightarrow \infty} f^2(n)\cdot n=0$$ so we have $f^2\in o(n^{-1})$. – Peter May 05 '17 at 12:57
-
Not sure, but I think the behaviour of $nf$ depends on $f$ – Peter May 05 '17 at 12:59
-
I think by multiplying and dividing by $n$, one has $$\lim_n \frac{n f(n)}{\frac{n}{\sqrt{n}}} = \lim_n \frac{n f(n)}{\sqrt{n}} = 0$$ So $n f \in \operatorname{o}(\sqrt{n})$. – Alex Vong May 05 '17 at 13:55
-
@AlexVong $n^{-1/2}=\frac{1}{\sqrt{n}}$ – Peter May 05 '17 at 13:57
1 Answers
0
We have, if $f\in \mathcal{o}(a(n))$ and $g\in \mathcal{O}(b(n))$, then $f g\in \mathcal{o}(a(n)b(n))$. Also, $\mathcal{o}(a(n)) \subset \mathcal{O}(a(n))$. These two facts will give you the limiting behaviors you want to find. Note $n\in \mathcal{O}(n)$.
Somos
- 35,251
- 3
- 30
- 76