limit of f(n) / g(n) is a constant, which function is larger?

Question

I want to figure out which function is larger between $f(n)$ and $g(n)$

One way to do this is to take the $lim_{n \rightarrow \infty} \frac{f(n)}{g(n)}$. If it turns out $\infty$ is in the numerator, we know $f(n) > g(n)$, if $\infty$ is in the denominator, we know $g(n) > f(n)$.

What if $lim_{n \rightarrow \infty} \frac{f(n)}{g(n)} = C$, where C is a constant? Which function is larger towards $\infty$? What if $C = 1$?

Answer 1

1. It depends on $C$.
2. In the given conditions, the given limit concerns only the tail of a sequence, we can make meaningful conclusion about the tail of the sequence. (i.e. an assertion on the sequence except finitely many terms, which is already good since we have the general truth for infinitely many terms.)

 

• $C < 1$: Fix $\epsilon > 0$ so that $C + \epsilon \le 1$. for sufficiently large $n$, $C-\epsilon < \dfrac{f(n)}{g(n)} < C+\epsilon$, so $f(n) < (C + \epsilon) g(n) \le g(n)$.
• $C = 1$: No conclusion. (Think of $\dfrac{n}{n+1} \sim 1 \sim \dfrac{n}{n-1}$)
• $C > 1$: Take reciprocal to get $\dfrac{g(n)}{f(n)} \to \dfrac1C < 1$. Apply the first case to get $g(n) < f(n)$ for sufficiently large $n$.