Prove that limits can be used for asymptotic analysis

Question

True or false:

If f(n)=$\Theta$(g(n)), then $$\lim_{n\rightarrow \infty}\frac{f(n)}{g(n)}$$ exists and is equal to some real number.

I'm not sure what needs to be done to demonstrate this. I do understand the laws of limits and properties of limits.

Answer 1

As an expansion on the perfect comments of Daniel and Crostul. Consider the function:

$$\begin{cases}f:\Bbb N\to\Bbb N \\ 2k\mapsto 3k \\ 2k+1\mapsto 2k\end{cases}$$ $$\begin{cases} g: \Bbb N\to\Bbb N \\ n\mapsto n\end{cases}$$

This sequence has $f=\Theta(g)$ by definiting, because

$$|f(n)|\le 2|g(n)|$$ for every $n$, and similarly for every $n$. $$|g(n)|\le 2|f(n)|$$

Now, for a limit to exist, we need that the value of ${f(n)\over g(n)}$ approaches some number as $n\to\infty$.

However, if $n$ is even, the ratio

$${f(2k)\over g(2k)}={3k\over 2k}={3\over 2}$$

and if $n$ is odd, the ratio is

$${f(2k+1)\over g(2k+1)}={2k\over 2k+1}\stackrel{k\to\infty}{\longrightarrow} 1$$

Formally this is written

$$\limsup_{n\to\infty} {f\over g} = {3\over 2} \\ \liminf_{n\to\infty} {f\over g} = 1$$

because the "biggest" limit you could get is ${3\over 2}$ and the "smallest" is $1$, but you don't need to know the terminology for that.

In either case, the limit does not exist for the same reason

$$\lim_{x\to\infty}\sin x$$

does not: it never approaches anything, it just bounces back and forth between two values.

---

Addendum: I chose this function because it actually has non-trivial computations for limits. If you want the "pocket" answer, it's even easier:

Let $f(n) = 1$ no matter what $n$ is and let $g(n) = (-1)^n$ so that

$$|f(n)|\le |g(n)|\le |f(n)|$$

immediately verifying $f(n)=\Theta(g(n))$, but the limit of the ratio bounces back and forth between $\pm 1$ forever.