What is Asymptotic Notation? Types of asymptotic notations.
Asymptotic notation describes the algorithm efficiency and performance in a meaningful way. It describes the behaviour of time or space complexity for large instance characteristics.
The order of growth of the running time of an algorithm gives a simple character of the algorithm’s efficiency and also allows allow us to compare relative performance of alternative algorithm. we call it growth function as we ignore the very small constant. The asymptotic running time of an algorithm is defined in terms of functions.
The asymptotic notation of an algorithm is classified into 3 types:
(i) Big Oh notation(O): (Asymptotic Upper bound) The function f(n)=O(g(n)), if and only if there exist a positive constant C and K such that f(n) ≤ C * g(n) for all n, n≥K.
(ii) Big Omega notation(Ω): (Asymptotic Lower bound) The function f(n)=Ω(g(n)), if and only if there exist a positive constant C and K such that f(n)≥C * g(n) for all n, n≥K.
(iii) Big Theta notation(θ): (Asymptotic Tight bound) The function f(n)=θ(g(n)), if and only if there exist a positive constant C1, C2 and K such that C1*g(n) ≤ f(n) ≤ C2 * g(n) for all n, n≥K.