Introduction to Asymptotic Analysis and Big (O)

We have seen that the time complexity of an algorithm can be expressed as a polynomial. To compare two algorithms, we can compare the respective polynomials. However, the analysis performed in the previous lessons is a bit cumbersome and would become intractable for bigger algorithms that we tend to encounter in practice.

Asymptotic analysis

If the input size is really small, how bad can a poorly designed algorithm get, right? Therefore, mathematicians have a tool for this sort of analysis called the asymptotic notation. The asymptotic notation compares two functions say, $f(n)$ and $g(n)$ for very large values of $n$. This fits in nicely with our 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))$ (read as big oh of $g(n)$) if there exists some positive real constant $c$ and an integer $n_0 > 0$, 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 values of $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 us that for very large values of $n$, $f(n)$ will be at most within a constant factor of $g(n)$ ...