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))$ ...