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.

Can anyone give an example of a case where $f(n) = \Theta(g(n))$ for two positive functions and the limit $\lim\limits_{n \to \infty}\dfrac{f(n)}{g(n)}$ does not exist?

share|improve this question

3 Answers 3

up vote 8 down vote accepted

Sure, $f(n) = \sin n + 2$ whereas $g\equiv 1$. The point is that if $f \in \Theta (g)$ then for $n$ large enough you have that $f(n)/g(n)$ is bounded. However, a bounded sequence does not have to have a limit. So actually, you can take any bounded sequence that does not have a limit and construct a new counterexample.

share|improve this answer
    
Thanks. I wasn't sure if $\sin (n) = \Theta(1)$ –  Rokko Apr 4 '13 at 13:34
2  
Excuse me? Obviously $f\in O(g)$, but $g\notin O(f)$. –  Did Apr 4 '13 at 15:06
    
@Did: you're right. Better now? –  Ilya Apr 4 '13 at 15:17
    
@Rokko: as Did has mentioned, $\sin n$ is not even positive (as you asked), so we have to shift it up a bit. –  Ilya Apr 4 '13 at 15:27

Take $f(x) = \sin x$ and $g(x) = \cos x$. the limit does not exist because of preriodicity, but both functions are always $\Theta(1)$.

share|improve this answer
    
The question does not ask for $f$ and $g$ in $\Theta(1)$. –  Did Apr 4 '13 at 15:20

Try $f(2n)=g(2n+1)=2$ and $f(2n+1)=g(n)=1$.

Then $g(n)/2\leqslant f(n)\leqslant2g(n)$ for every $n$ hence $f\in\Theta(g)$ but $f(2n)/g(2n)=2$ while $f(2n+1)/g(2n+1)=1/2$ hence the sequence $(f(n)/g(n))_n$ diverges.

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.