Asymptotic analysis refers to defining the mathematical foundation of its run-time performance. Asymptotic analysis help conclude the best case, worst case and average case scenarios of an algorithm. In simple words, asymptotic analysis refers to computing the running time of any operation in mathematical units of computation.


The time required by an algorithm falls under three types:

Best Case: Minimum time is required for program execution.

Average Case: Average time is required for the program execution.

Worst Case: Maximum time is required for the program execution.

Asymptotic Notations

The most commonly used asymptotic notations used for calculating the time complexity of an algorithm are:

Big oh Notation (O)

This notation is used to define the upper boundary of an algorithm’s run time. It is used to measure the worst case of time complexity, i.e. the longest time that an algorithm takes to complete its execution.

 

Asymptotic Analysis

In the diagram above, for a function f(n)

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

 

Omega Notation ()

This notation is used to define the lower boundary of an algorithm’s run time. It is used to measure the best case of time complexity, i.e. the shortest time that an algorithm takes to complete its execution.

 

Asymptotic Analysis

In the diagram above, for a function f(n)

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

 

Theta Notation ()

This notation is used to define both the lower boundary and the upper boundary of an algorithm’s run time. It is used to measure the average case of time complexity.

 

Asymptotic analysis

In the diagram above, for a function f(n)

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

 

 

Common Asymptotic Notations

 

Constant - O(1)
Logarithmic - O(log n)
Linear - O(n)
N log n - O(n log n)
quadratic - O(n^2)
Cubic - O(n^3)
Polynomial - N^O(1)
Exponential - N^O(2)