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.

Suppose that I want to show that $g(n) \in O(f(n))$ as $n\rightarrow\infty$ for functions $f(n),g(n)>0$. I know that this means that there exists a constant $c$ such that for all sufficiently large $n$ it holds that $g(n) \leq c f(n)$. Moreover, according to wikipedia this is equivalent to $\lim\sup_{n\rightarrow\infty}\left|\frac{g(n)}{f(n)}\right| < \infty$.

However, even if I can show that $\lim_{n\rightarrow\infty}\left|\frac{g(n)}{f(n)}\right| = c < \infty$, this also implies $g(n) \in O(f(n))$, since from this it follows that $g(n) < (c+\epsilon)f(n)$, for sufficiently large $n$ and any $\epsilon>0$.

Could someone give me an example where the first condition (using $\lim\sup$) holds but the second one (using only $\lim$) does not?

share|improve this question
1  
I think you want to require a bit more about $f$ and $g$, for example that they take on only positive values. For example, if $f$ and $g$ are always 0, any $c$ will make the first definition trivially true, but the $\lim \sup$ definition will fail because the quotient is undefined. –  Hew Wolff Oct 16 '12 at 3:41

3 Answers 3

up vote 2 down vote accepted

Or somewhat more simply, how about $g(n) = 1$ (if $n$ is even), $2$ (if $n$ is odd); and $f(n) = 2$. $g / f$ bounces between $1/2$ and $1$, so it's bounded, but it has no limit.

share|improve this answer

$g(n) = \sin(n)$ and $f(n) = 2 + \sin(n)$.

share|improve this answer

Let $g(n)=n$ when $n$ is even, and let $g(n)=n^2$ when $n$ is odd. Let $f(n)=n^2+1$. The limit of $\frac{f(n)}{g(n)}$ as $n\to\infty$ does not exist.

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.