Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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!

share|improve this question

2 Answers 2

up vote 4 down vote accepted

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,

share|improve this answer
    
thanks Patrick great answer –  user19821 Nov 21 '11 at 4:42
    
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! =) –  Patrick Da Silva Nov 21 '11 at 5:54

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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