Analysis and Big-O notation

In CS 170, we commonly work with two formulations of asymptotic notation, as described in Discussion 1:

Formulation 1: Definition

$f(n) = O(g(n))$ if there exists a $c > 0$ where after large enough $n$, $f(n) \leq c \cdot g(n)$. Asymptotically, $f$ grows at most as much as $g$.

Formulation 2: Convenient condition

If $f(n), g(n) \geq 0$ and $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$, then $f(n) = O(g(n))$.

The discussion asks you to show yourself that these formulations are correct, and that Formulation 2 is a sufficient (but not necessary) condition for Formulation 1, given that $\lim_{n \to \infty} \frac{f(n)}{g(n)}$ exists. However, this requires a bit of real analysis, which is not a prerequisite of this class. Therefore, I wrote this brief note to provide a bit of mathematical justification for this idea. For a more detailed look at this, check out the last few pages of this excellent note from COMP 250 at McGill, which I have essentially paraphrased here.

First, the formal definition of a limit.

Limit

A sequence $f(n)$ of real numbers converges to (or has a limit of) a real number $f_\infty$ if, for any $\epsilon > 0$, there an exists an $n_0$ such that for all $n \geq n_0$, $|f(n) - f_\infty| < \epsilon$.

We would like to relate this definition of the limit to our previous definition of Big-O. To do this, let us write the definition of Big-O slightly differently, in terms of the ratio of $f(n)$ to $g(n)$.

Big-O (altered definition)

$f(n)$ is $O(g(n))$ if there exists a $c$ such that after large enough $n$,

$$\frac{f(n)}{g(n)} \leq c.$$

Now, assume that $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$, and $f(n), g(n) \geq 0$. Based on the definition of the limit, we have that, for sufficiently large $n$ and arbitrary $\epsilon > 0$,

$$\left|\frac{f(n)}{g(n)} - 0\right| < \epsilon \implies \left|\frac{f(n)}{g(n)}\right| < \epsilon.$$

Does this look similar to our altered Big-O definition? Indeed, take an arbitrary $\epsilon$ and call it $c$. Then we have

$$\frac{f(n)}{g(n)} < c,$$

which tells us (up to an inconsequential equality) that

$$\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0 \implies f(n) = O(g(n)).$$

This line of reasoning can be extended to the similar formulations of Big-$\Omega$ and Big-$\Theta$, described in Section 1 of the discussion. I won't go over them here, but you can refer to page 13 of the McGill note if you'd like to see it worked out completely.

Hope this note was helpful!

<<<