Overview
Asymptotic notations are the mathematical notations to represent order of growth of any mathematical functions during asymptotic analysis. We can represent using following three notations and they are as follows:
- Big O Notation: which represents exact or upper bound of order of growth.
- Theta θ Notation: which represent exact order of growth.
- Omega Ω Notation: which represent exact or lower bound of order of growth.
Keynote:-
- When we say order of growth is, O(n) It takes either linear time or less than linear time.
- When we say order of growth is, θ(1) It takes either constant time or higher than constant time.
- Big O and Omega notation are the opposite of each other.
Since we talk about best case, average case and worst case, we are most of the time interested in upper bounds. That’s why Omega notation is not used much. It is rarely used in the analysis of algorithms. Most of the time we will see Big O notation and Theta notation because Theta notation gives us an exact bound and Big O notation gives us an upper bound. So most of the time either we are interested in knowing the exact bound or knowing the upper bound.
Important
During calculation of order of growth most of the time we omit omega notation and do use Big O notation which helps to identify maximum time taken by algorithm during execution.
Conclusion
In this post, we learn the three asymptotic notations used to analyze the algorithm.