Doubt in Proof that Limit of two functions going to infinity converges to a positive constant.

Question

STATEMENT : Limit of two functions going to infinity converges to a positive constant.

---

PROOF : We will use the fact that the limit exists and is positive to show that $f (n) = O(g(n))$ and $f (n) = \Omega(g(n))$, as required by the definition of $\Theta(\cdot)$.
Since $$\lim\limits_{n \to\infty} \frac{f(n)}{g(n)}=c>0,$$ it follows from the definition of a limit that there is some $n_0$ beyond which the ratio is always between $\frac 12c$ and $2c$. Thus, $f(n) \le 2cg(n)$ for all $n \ge n_0$, which implies that $f (n) = O(g(n))$;

and $f (n) \ge \frac 12cg(n)$ for all $n \ge n_0$, which implies that $f (n) = \Omega(g(n))$.

---

DOUBT : Can someone please explain a bit why there is some $n_0$ beyond which the ratio is always between $\frac 12c$ and $2c$?

Answer 1

That's the very definition of $\lim_{n\to \infty} h(n) = c$.

That means for any value $\epsilon > 0$ we can find some value $n_0$ so that for all $n > n_0$ ir will always be then case that $c-\epsilon < h(n) < c +\epsilon$.

There's nothing to explain why, because that is what $\lim_{n\to \infty} h(n) = c$ means.

So $\lim_{n\to \infty} \frac {f(n)}{g(n)} = c$ then we can find for ANY $\epsilon > 0$, in particular for $\epsilon = \frac 12 c$, there is some $n_0$ so that for all $n > n_0$ we will always have:

$c - \epsilon < \frac {f(n)}{g(n)} < c + \epsilon$ so

$c - \frac 12 c < \frac {f(n)}{g(n)} < c + \frac 12c $ so

$\frac 12 c < \frac {f(n)}{g(n)} < \frac 32c < 2c$

Answer 2

This is just a quick and dirty version of an $\epsilon\text{-}\delta$ argument; the fact that $c>0$ means that $\epsilon_1=c/2>0$ and $\epsilon_2=c>0$ are both valid "choices" for the limit definition, and then the rest falls into place.