Introduction to Asymptotic Analysis and Big O

You have seen that the time complexity of an algorithm can be expressed as polynomial. To compare two algorithms, you can compare the respective polynomials. However, the analysis performed in the previous lessons is cumbersome and would become intractable for bigger algorithms that are normally encountered in practice.

Asymptotic analysis

One observation that may help is that you want to worry about large input sizes only. If the input size is really small, how bad can a poorly designed algorithm get, right? Mathematicians have a tool for this sort of analysis called asymptotic notation. The asymptotic notation compares two functions; let’s say, $f(n)$ and $g(n)$ for large values of $n$. This fits in nicely with your need for comparing algorithms for very large input sizes.

Big O notation

One of the asymptotic notations is the “Big O” notation. A function $f(n)$ is considered $O(g(n))$, which is read as Big Oh of $g(n)$. If a positive real constant $c$ and an integer $n_0> 0$ exists, such that the following inequality holds for all $n \geq n_0$:

$f(n) \leq cg(n)$

The following graph shows a plot of a function $f(n)$ and $cg(n)$ that demonstrates this inequality.

Note that the above inequality does not have to hold for all $n$. For $n < n_0$, $f(n)$ is allowed to exceed $cg(n)$ but for all values of $n$ beyond some value $n_0$, $f(n)$ is not allowed to exceed $cg(n)$.

What good is this? It tells you that for large values of $n$, $f(n)$ will be within a constant factor of $g(n)$ ...