Types of Asymptotic Notations in Complexity Analysis of Algorithms,

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.