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?

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Hew Wolff Oct 16 '12 at 3:41
2
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
1
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.