Asymptotic analysis is the mathematical framing of an algorithm’s run-time performance. An asymptotic analysis computes the run time of any operation in mathematical units of computation. Using this, we can conclude the best, worst, and average-case scenarios of a given algorithm.
Asymptotic analysis is input bound. If there is no input to the algorithm, it is concluded to work in constant time. All other factors are considered constant other than input.
For example, when computing an asymptotic analysis between f(n) and g(n²) run time, the former will involve run time increasing linearly with the increase in n and the latter exponentially with the increase of n. The run time of both operations can be nearly the same if n is small.
Common Notations for Asymptotic Analysis:
Big O Notation, O
The upper bound of an algorithm’s run time. It measures the worst-case time complexity or the longest amount of time an algorithm can possibly take to complete. tldr: worst case run time
Omega Notation, Ω
The lower bound of an algorithm’s run time. It measures the best case time complexity or the best amount of time an algorithm can possibly take to complete. tldr: best case run time
Theta Notation, θ
Theta notation combines upper bounds with lower bounds to get tight bounds. It provides the average time complexity of an algorithm.
History
This family of notations was invented by Paul Bachmann, Edmund Landau, and is collectively also called Bachmann–Landau notation.
