Types of Asymptotic Notations in
Complexity Analysis of Algorithms
Asymptotic Notation is a way of comparing function that ignores constant
factors and small input sizes.
For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is
linear i.e. the best case.
There are mainly three asymptotic notations:
1. Big-O Notation (O-notation)
2. Omega Notation (Ω-notation)
3. Theta Notation (Θ-notation)
Big-O Notation (O-notation)
Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives
the worst-case complexity of an algorithm.
If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
Omega Notation (Ω-notation)
Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.
Complexity Analysis of Algorithms
Asymptotic Notation is a way of comparing function that ignores constant
factors and small input sizes.
For example: In bubble sort, when the input array is already sorted, the time taken by the algorithm is
linear i.e. the best case.
There are mainly three asymptotic notations:
1. Big-O Notation (O-notation)
2. Omega Notation (Ω-notation)
3. Theta Notation (Θ-notation)
Big-O Notation (O-notation)
Big-O notation represents the upper bound of the running time of an algorithm. Thus, it gives
the worst-case complexity of an algorithm.
If f(n) describes the running time of an algorithm, f(n) is O(g(n)) if there exist a positive
constant C and n0 such that, 0 ≤ f(n) ≤ cg(n) for all n ≥ n0
Omega Notation (Ω-notation)
Omega notation represents the lower bound of the running time of an algorithm. Thus, it
provides the best case complexity of an algorithm.
