# Asymptotic Notation

This guide will introduce how to formally prove asymptotic relationships. It presupposes a basic knowledge of asymptotic notation. Minimally, you should be vaguely familiar with what $O\left(n\right)$ or $\Theta (nlogn)$ means.

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 symbols^{2} characterise the relationship between functions: $\omega $, $\Omega $, $\Theta $, $O$, $o$. The asymptotic symbols are comparable to $>$, $\ge $, $=$, $\le $, $<$ respectively. The only difference between numerical and asymptotic relationships is the asymptotic symbols describe the limiting relationship as inputs grow in size.

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.

## Using the scalar multiple definition

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

Consider the following 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$.

- In the symbol table we see the inequality associated with $O$ is $\left|f\left(n\right)\right|\le M\left|g\left(n\right)\right|$.
- We use the given information to get: $|4{n}^{2}+3n+2|\le M|2{n}^{2}+n|$.
- Try different values for $M$.
- 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$.
- 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.
- 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)\Rightarrow 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)\Rightarrow 9\le 9$. The inequality holds for this choice of ${n}_{0}$.

- 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\Rightarrow 2\le 2{n}^{2}\Rightarrow {n}^{2}\ge 1$. Since the square of $n$ is larger than $1$ for all $n\ge 1$, the inequality holds.

## Using the limit definition

**Consider**the $\underset{n\to \infty}{lim}\frac{f\left(n\right)}{g\left(n\right)}$.**Substitute**the function bodies.**Evaluate**the limit, typically using: properties of the limit, reduction to known limits, L’Hôpital’s rule^{3}.**Verify**that the result of the limit is within the range of the asymptotic symbol.

Consider the following 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}$.

- We have the $\underset{n\to \infty}{lim}\frac{f\left(n\right)}{g\left(n\right)}$.
- We use the given information to get: $\underset{n\to \infty}{lim}\frac{{n}^{2}}{{e}^{n}}$.
- 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$.
- We see the interval associated with $O$ from the symbol table is $[0,\infty )$. The value $0$ is within the interval so the relationship holds.

## Symbol table

Symbol | Interval | Inequality |

$\omega $ | $\infty $ | $\left|f\left(n\right)\right|\ge M\left|g\left(n\right)\right|$ for all $M$ |

$\Omega $ | $(0,\infty ]$ | $\left|f\left(n\right)\right|\ge M\left|g\left(n\right)\right|$ for some $M$ |

$\Theta $ | $(0,\infty )$ | ${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$ | $[0,\infty )$ | $\left|f\left(n\right)\right|\le M\left|g\left(n\right)\right|$ for some $M$ |

$o$ | $0$ | $\left|f\left(n\right)\right|\le M\left|g\left(n\right)\right|$ for all $M$ |