Asymptotic Notations

Asymptotic Notations:

Asymptotic analysis of an algorithm refers to defining the mathematical bounds of its run-time performance. 

Using asymptotic analysis, the best case, average case, and worst case scenario of an algorithm can be given.

Asymptotic analysis is input bound i.e., if there's no input to the algorithm, it is concluded to work in a constant time. Other than the "input" all other factors are considered constant.

Asymptotic analysis refers to computing the running time of any operation in mathematical units of computation.

       Generally, the time required by an algorithm falls under three types −

Best Case − Minimum time required for program execution.

Average Case − Average time required for program execution.

Worst Case − Maximum time required for program execution.

The commonly used asymptotic notations to calculate the running time complexity of an algorithm.

1)      Ο Notation

2)      Ω Notation

3)      θ Notation

1)      Big Oh Notation (Ο)

    The notation Ο(n) is the formal way to express the upper bound of an algorithm's running time. It              measures the worst case time complexity or the longest amount of time an algorithm can possibly take      to complete. We use O-notation to give an upper bound on a function, to within a constant factor.

                                          

    For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c > 0 and n₀ such that f(n) ≤ c.g(n) for all n > n₀. }

2)      Omega Notation (Ω)

      The notation Ω(n) is the formal way to express the lower bound of an algorithm's running time. It              measures the best case time complexity or the best amount of time an algorithm can possibly take to        complete. Ω-notation provides an asymptotic lower bound.

                                         

       For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

3)      Theta Notation (θ)

      The notation θ(n) is the formal way to express both the lower bound and the upper bound of an                  algorithm's running time. The θ-notation asymptotically bounds a function from above and below. 

       It is represented as follows −

                                          

θ(f(n)) = { g(n) if and only if g(n) =  Ο(f(n)) and g(n) = Ω(f(n)) for all n > n₀. }

Basic efficiency classes:

The time efficiencies of a large number of algorithms fall into only a few classes.