Introduction to Asymptotic Analysis and Big O
In this lesson, we will learn about asymptotic notation, an important tool applied to the analysis of algorithms.
We know that the time complexity of an algorithm can be expressed as a polynomial. To compare the two algorithms, we can compare the respective polynomials.
Asymptotic Analysis
One observation that helps us is that we 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 the asymptotic notation. The asymptotic notation compares two functions, say, and for very large values of . 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 is considered , read as big oh of , if there exists some positive real constant and an integer , such that the following inequality holds for all :
The following graph shows a plot of a function and that demonstrates this inequality.