# Question about $\Theta$

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?

-

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.

-
Thanks. I wasn't sure if $\sin (n) = \Theta(1)$ – Rokko Apr 4 '13 at 13:34
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)$.

-
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.

-