Asymptotic Notations are mathematical notations used to describe the running time of an algorithm based on the increasing input size.

In asymptotic analysis, we check whether it is linear, quadratic or exponential in the size of the input. With the increasing size of the input , the asymptotic efficiency of algorithms is studied ignoring the constant factors.

There are three different notations – Big O (O) , Big Omega (Ω), Big theta (θ)

Big O Notation (O) –

It is used to define the upper bound of an algorithm in terms of time complexity. It explains the maximum amount of time an algorithm requires to process any input of given size n. Big O Notation describes the worst case time complexity of an algorithm.

Considering a function f(n) as time complexity of an algorithm and g(n) as the most significant term.

Therefore,  f(n)<= c g(n) ∀ n>n₀ , c>0 and n₀ >=1, where c is a +ve constant, f(n)=O(g(n))

Big Omega Notation (Ω) –

It is used to define the lower bound of an algorithm in terms of time complexity. It describes the minimum amount of time required by an algorithm for any input of given size n. Big Omega Notation describes the best case time complexity of an algorithm. 

Considering a function f(n) as time complexity of an algorithm and g(n) as the most significant term.

Therefore,  f(n)>= c g(n) ∀ n>n₀ , c>0 and n₀ >=1, where c is a +ve constant, f(n)=Ω(g(n))

Big Theta Notation (θ) –

It is used to define the tight bound of an algorithm in terms of time complexity. It describes the average time required by an algorithm for all input values. Big theta notation describes the average case time complexity of an algorithm. 

Considering a function f(n) as time complexity of an algorithm and g(n) as the most significant term.

Therefore, c1 g(n) <= f(n)<= c2 g(n) ∀ n>n₀ , c1,c2>0 and n₀ >=1, where c1,c2 are +ve constant, f(n)=θ(g(n))