3
$\begingroup$

Sorry about yet another big-Oh notation question, I just found it very confusing.

If $T(n)=\frac{5}{n}$, is it true that $T(n)=O(\frac{1}{n})$ and $T(n) = o(1)$? I think so because (if $h(n)=\frac{1}{n}$)

$ \lim_{n \to \infty} \frac{T(n)}{h(n)}=\lim_{n \to \infty} \frac{\frac{5}{n}}{\frac{1}{n}}=5>0 , $

therefore $T(n)=O(h(n))$.

At the same time (if $h(n)=1$)

$ \lim_{n \to \infty} \frac{T(n)}{h(n)}=\frac{(\frac{5}{n})}{1}=0, $

therefore $T(n)=o(h(n))$.

Thanks!

2 Answers 2

4

If $x_n = O(1/n)$, this means there exists $N$ and $C$ such that for all $n > N$, $|x_n| \le C|1/n|$. Hence $ \lim_{n \to \infty} \frac{|x_n|}{1} \le \lim_{n \to \infty} \frac{C|1/n|}{1} = 0. $ This means if $x_n = O(1/n)$ then $x_n = o(1)$.

Conversely, it is not true though. Saying that $x_n = o(1)$ only means $x_n \to 0$, but there are sequences that go to zero and are not $O(1/n)$ (think of $1/\sqrt{n}$ for instance).

Hope that helps,

  • 0
    I don't know if you knew the definitions or just worked by intuition, but I don't think it's pretty hard to work those things out if you're in the right frame of mind. You could've probably answered it yourself if you asked yourself the right questions, it's a matter of time before you do! Glad I could help though! =)2011-11-21
0

$\frac{1}{n}=o(1)$ and therefore if $f=O(\frac{1}{n})$ than $f=o(1)$.