Asymptotic analysis
of an algorithm refers to defining the mathematical boundation/framing of its
run-time performance. Using asymptotic analysis, we can very well conclude the
best case, average case, and worst-case scenario of an algorithm.
Asymptotic analysis is input bound i.e. if there's no input
to the algorithm, it is concluded to work in a constant time. Other than the
"input" all other factors are considered constant.
Asymptotic analysis refers to computing the running time of
any operation in mathematical units of computation. For example, the running
time of one operation is computed as f(n)
and maybe for another operation, it is computed as g(n2). This
means the first operation running time will increase linearly with the increase
in n and the running time of the second operation will increase exponentially
when n increases. Similarly, the running time of both operations will be nearly
the same if n is significantly small.
Usually, the time required by an algorithm falls under three
types
- Best Case - Minimum time required for program execution.
- Average Case - Average time required for program execution.
- Worst Case - The maximum time required for program execution.
Asymptotic Notations
Following are the commonly used asymptotic notations to
calculate the running time complexity of an algorithm.
O
Notation
Ω Notation
Θ Notation
Big Oh Notation, O
The notation O(n)
is the formal way to express the upper bound of an algorithm's running time. It
measures the worst-case time complexity or the longest amount of time an algorithm
can possibly take to complete.
Omega Notation, Ω
The notation (n) is the formal way to express the lower
bound of an algorithm's running time. It measures the best case time complexity
or the best amount of time an algorithm can possibly take to complete.
Theta Notation, Θ
The notation
Common Asymptotic Notations
Following is a list of some common asymptotic notations –
Logarithmic |
O(log n) |
Linear |
O(n) |
n log n |
O( n log n) |
Quadratic |
O(n2) |
Cubic |
O(n3) |
Polynomial |
No(1) |
Exponential |
2o(n) |