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.