What is Asymptotic Notation? Types of asymptotic notations.

Mintu Konwar
2 min readFeb 20, 2019

--

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.

[Big Oh Notation (f(n) ≤ C * g(n))]

(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.

[Omega (f(n)=Ω(g(n))) notation]

(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.

[Big Theta notation (C1*g(n) ≤ f(n) ≤ C2 * g(n))]

--

--

Mintu Konwar
Mintu Konwar

Written by Mintu Konwar

A third-year MCA student at Dibrugarh University with an interest in cybersecurity, software development, IT, and Machine Learning.

No responses yet