Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|improve this question
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|cite|improve this answer
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)$.

share|cite|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|cite|improve this answer

Your Answer


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.