Asymptotic Notation in Data Structure
Written by
What are Asymptotic Notations?
The Time complexity of Algorithms
Space Complexity of an Algorithm
What are Asymptotic Notations?
Asymptotic notations are mathematical notations or expressions that are used to describe the running rime or better called as the complexity of an algorithm for the input, for which the algorithm takes time.
The efficiency of an algorithm depends on the amount of time, storage and other resources required executing the algorithm. The efficiency is measured with the help of asymptotic notations.
The study of change in performance of the algorithm with a change in the order of the input size is defined as Asymptotic Analysis.
Example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is minimum and thus is considered as the best case. But if the same input array is reversed, then the algorithm takes the maximum time to sort the array, this scenario is the worst-case scenario.
Another case could be where the input array is jumbled and is in no particular order, them the algorithm takes average time to sort the array.
These durations taken by the algorithm to sort the array denoted using Asymptotic Notations.
# There are 3 types of Asymptotic Notations:
- Theta (Θ) Notation encloses both upper bound and lower bound of an algorithm; it is used for analyzing the average-case complexity of an algorithm.
- Omega (Ω) Notation shows the best case in the algorithm running time. It represents the lower bound running time complexity of an algorithm.
- Big O Notation describes the worst case for the algorithm. It represents the upper bound running time complexity of an algorithm.
