Introduction to Asymptotic Analysis and Big O
Explore the concepts of asymptotic analysis and Big O notation to understand how to evaluate and compare algorithm time complexities. This lesson teaches you how to simplify complexity expressions to focus on large input sizes, helping you assess algorithm performance using practical examples and detailed explanations.
We'll cover the following...
We have seen that the time complexity of an algorithm can be expressed as a polynomial. To compare two algorithms, we can compare their 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
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 ...