# Asymptotic Notation

This guide will introduce how to formally prove asymptotic relationships. See begriffs’ introduction of asymptotics if you’re a little rusty.

When we write computer programs, we need a way to describe the relative performance of different algorithms. We need to do so in a way that is machine independent and ignores irrelevant factors.1 Asymptotic notation is a short description of an algorithm’s performance as a function of its input. It is a convenient and mathematically precise notation. All computer scientists describe algorithms in terms of asymptotic performance.

Five symbols2 characterise the relationship between functions: $\omega$, $\Omega$, $\Theta$, $O$, $o$. The asymptotic symbols are comparable to $>$, $\ge$, $=$, $\le$, $<$ respectively. The difference between numeric and asymptotic relationships are that asymptotic symbols describe the limiting relationship as inputs grow in size. Given below is a table summarizing the asymptotic relationships.

 Symbol Interval Inequality $\omega$ $\infty$ $|f\left(n\right)|\ge M|g\left(n\right)|$ for all $M$ $\Omega$ $\left(0,\infty \right]$ $|f\left(n\right)|\ge M|g\left(n\right)|$ for some $M$ $\Theta$ $\left(0,\infty \right)$ ${M}_{1}g\left(n\right)\le f\left(n\right)\le {M}_{2}g\left(n\right)$ for some ${M}_{1}$, ${M}_{2}$ $O$ $\left[0,\infty \right)$ $|f\left(n\right)|\le M|g\left(n\right)|$ for some $M$ $o$ $0$ $|f\left(n\right)|\le M|g\left(n\right)|$ for all $M$

Let’s take the most popular symbol, $O$, and prove $f\left(n\right)\in O\left(g\left(n\right)\right)$ for some functions $f\left(n\right)$ and $g\left(n\right)$. We can approach the proof in a number of ways.

Method. The most formal method is using the scalar multiple definition.

1. Identify the inequality associated with the asymptotic symbol.
2. Substitute the function bodies.
3. Attempt different values for $M$ until the relationship holds for some input ${n}_{0}$.
4. Verify that the inequality stays true for all numbers greater than ${n}_{0}$.

Example. Prove that $f\left(n\right)\in O\left(g\left(n\right)\right)$ where $f\left(n\right)=4{n}^{2}+3n+2$ and $g\left(n\right)=2{n}^{2}+n$.

1. In the table we see the inequality associated with $O$ is $|f\left(n\right)|\le M|g\left(n\right)|$.
2. We use the given information to get: $|4{n}^{2}+3n+2|\le M|2{n}^{2}+n|$.
3. Try different values for $M$.
1. Let $M=1$. Is $|4{n}^{2}+3n+2|\le |2{n}^{2}+n|$? This seems unlikely given the coefficient on the high-order term is greater in $4{n}^{2}+3n+2$.
2. Let $M=2$. Is $|4{n}^{2}+3n+2|\le 2|2{n}^{2}+n|$? Now the high-order coefficients are both $4$, but the expression $4{n}^{2}+3n+2$ still has a larger second-order term.
3. Let $M=3$. Is $|4{n}^{2}+3n+2|\le 3|2{n}^{2}+n|$? This seems more promising. Given ${n}_{0}=0$, $4{\left(0\right)}^{2}+3\left(0\right)+2\le 3\left(2\right){\left(0\right)}^{2}+3\left(0\right)⇒2\le 0$ which does not hold. However, given ${n}_{0}=1$, $4{\left(1\right)}^{2}+3\left(1\right)+2\le 3\left(2\right){\left(1\right)}^{2}+3\left(1\right)⇒9\le 9$. The inequality holds for this choice of ${n}_{0}$.
4. Can we show $|4{n}^{2}+3n+2|\le 3|2{n}^{2}+n|$ for all $n\ge 1$? We remove the absolute values because the functions are monotonically increasing at the points in question. $4{n}^{2}+3n+2\le 6{n}^{2}+3n⇒2\le 2{n}^{2}⇒{n}^{2}\ge 1$. Since the square of $n$ is larger than $1$ for all $n\ge 1$, the inequality holds.

Method. There is an alternate method I found more intuitive. This is the limit method.

1. Consider the $\underset{n\to \infty }{lim}\frac{f\left(n\right)}{g\left(n\right)}$.
2. Substitute the function bodies.
3. Evaluate the limit in any way possible, for example, using properties of the limit, reduction to known limits, or L’Hôpital’s rule3.
4. Verify that the result of the limit is within the range of the asymptotic symbol.

Example. Prove that $f\left(n\right)\in O\left(g\left(n\right)\right)$ where $f\left(n\right)={n}^{2}$ and $g\left(n\right)={e}^{n}$.

1. We have the $\underset{n\to \infty }{lim}\frac{f\left(n\right)}{g\left(n\right)}$.
2. We use the given information to get: $\underset{n\to \infty }{lim}\frac{{n}^{2}}{{e}^{n}}$.
3. We apply L’Hopital’s rule because the limit gives an indeterminate form $\frac{\infty }{\infty }$: $\underset{n\to \infty }{lim}\frac{2n}{{e}^{n}}$. We apply it again: $\underset{n\to \infty }{lim}\frac{2}{{e}^{n}}$. The numerator is constant while the denominator monotonically increases. The limit is therefore $0$.
4. We see the interval associated with $O$ from the symbol table is $\left[0,\infty \right)$. The value $0$ is within the interval so the relationship holds.