1. What is Asymptotic Notations?
Asymptotic Notations are languages that allow us to analyze an algorithm’s run-time performance. Asymptotic Notations identify running time by algorithm behavior as the input size for the algorithm increases. This is also known as an algorithm’s growth rate. 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 − Maximum time required for program execution.
2. Types of Asymptotic Notation
Following are the commonly used asymptotic notations to calculate the running time complexity of an algorithm.
- Ο Notation (Big-O Notation)
- Ω Notation (Big-Omega Notation)
- θ Notation (Theta Notation)
2.1 Ο Notation (Big-O Notation)
Big-O, commonly written as O, is an Asymptotic Notation for the worst case, or the longest amount of time an algorithm can possibly take to complete.. It provides us with an asymptotic upper bound for the growth rate of run-time of an algorithm.
For example, for a function f(n)
Ο(f(n)) = { g(n) : there exists c > 0 and n0 such that f(n) ≤ c.g(n) for all n > n0. }
You can read more about Big-Oh Notation here.
2.2 Ω Notation (Big-Omega Notation)
Big-Omega, commonly written as Ω, is an Asymptotic Notation for the best case, or the best amount of time an algorithm can possibly take to complete. It provides us with an asymptotic lower bound for the growth rate of run-time of an algorithm.
For example, for a function f(n)
Ω(f(n)) ≥ { g(n) : there exists c > 0 and n0 such that g(n) ≤ c.f(n) for all n > n0. }
2.3 θ Notation (Theta Notation)
Theta, commonly written as Θ, is an Asymptotic Notation to denote the asymptotically tight bound (lower bound and the upper bound) on the growth rate of run-time of an algorithm.
For example, for a function f(n)
θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all n > n0. }
3. Common Asymptotic Notations
Following is a list of some common asymptotic notations −
| Notation | Name |
|---|---|
| O(1) | constant |
| O(log n) | logarithmic |
| O(n) | linear |
| O(n log n) = O(log n!) | linearithmic, loglinear, or quasilinear |
| O(n2) | quadratic |
| O(nc) | polynomial or algebraic |
| O(cn); where c>1 | exponential |
| O(n!) | factorial |
4. Why Performance Analysis?
There are many important things that should be taken care of, like user friendliness, modularity, security, maintainability, etc. Why to worry about performance?
The answer to this is simple, we can have all the above things only if we have performance. So performance is like currency through which we can buy all the above things. Another reason for studying performance is – speed is fun!