What is Asymptotic Notation?

Asymptotic Notation:

It is a sorted way to Check the efficiency of each algorithm. It is way of represent the complexity of the algorithm. there are various notations such as.

1).   Big O  Notation 
2).   Omega Notation
3).    Theta Notation

for calculating the complexity of an algorithm, there are three cases :

1. Best Case :-    Minimum time required for program execution.

2. Average Case:-    Average time required for program execution.

3. Worst Case:-   Maximum time required for program execution.

1). Big O Notation :-     

1. It is denoted by 'O'.
2. It is the method of representing the upper bound of algorithm running time.
3. using Big O Notation we can give longest amount of time taken by algorithm to complete.

✷ How to calculate Complexity using Big O Notation.

Let f(n) and g(n) be two non-negative function. Let (n not) and constant (c) are two integer such that (n not) denotes some value of input and (n > n not ).

Similarly , c is some constant such that [ c > 0].

[ f(n) <= c* g(x) ]

Then f(n) is belong to Big O Notation of g(x).

[ f(n) Є O(g(x) ]  in other words f(n) is less then  g(x) &  

[ f(n) < g(x) ] if g(x) is multiple of some constant 'c' 

Omega Notation:

1. It is denote by 'Ω' .
2. This representing is used to represent ' lower bound' of algorithm running point.
3. Using  Ω ( omega)  Notation we can give shortest amount of time taken by algorithm.

Definition :-  Let f(n) is said to be Ω g(x). If f(n) is bounded below by some positive constant 'c' and multiple of g(n) such that

                                       [ f(n) >= c* g(x) ]       

Theta Notation (𝞡):      

1. It is denoted by '𝞡'.
2. It is the method of representing the running time of algorithm is between upper and lower bound .
3. Using Theta Notation we can denote average amount of time taken by an algorithm.
4. Let F(n) and g(x) is two non-negative function, these are two positive constant as c1 and c2.

                  [ c1 <= f(n)  <= [c2*g(x) ]  or, [c1 c g(x) ]<= f(n) <= [c2*g(x)]]

              then  we can say that                                                

    
Some Asymptotic Notation

1. Constant → o(1)
2. algorithm → o (log(x))
3. linear →    o(n)
4. quadratic → o(n²)
5. polynomial → n o(1)