2
$\begingroup$

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?

  • 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.2012-10-16

3 Answers 3

2

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.

1

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

1

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.