Asymptotic Notations

The asymptotic notations are the mathematical tool to represent time complexity of algorithm for asymptotic analysis.

There are mainly three notations used in algorithm analysis, which are:-

1. Big - O notation. 
2. Omega Ω notation.
3. Theta Θ notation.

Big - O notation 

The big - O notation always gives an upper bound for f(n) to within a constant factor.

Therefore, 

Here, 

O(g(n)) = {f(n): there exist positive constant c and n0 such that 0<=f(n)<=c*g(n) for all n>n0}

In this notation we considered worst case O(n^2) and best case O(n).

Omega Ω notation 

The omega Ω notation always gives a lower bound for a function f(n) to within a constant factor. In this notation only best case is considered.

The omega notation is the least used notation among all three. 

Ω (g(n)) = {f(n): there exist positive constants c and n0 such that 0 <= c*g(n) <=f(n) for all n >= n0}.

Theta Θ notation

In theta Θ notation, we always considered average case only. 

Theta notation bounds a function from above and below. 

Therefore, 

Θ(g(n)) = {f(n): there exist positive constants c1, c2 and n0 such that 0 <= c1*g(n) <= f(n)<= c2*g(n) for all n >= n0}.