Asymptotic Analysis

An algorithm’s asymptotic analysis refers to defining the mathematical boundation/framing of its run-time performance. We can very well conclude the best-case, average-case, and worst-case scenarios of an algorithm using asymptotic analysis.

Asymptotic analysis is input bound, which means that if the algorithm receives no input, it is assumed to work in a constant time. Except for the “input,” all other factors are assumed to be constant.

The computation of the running time of any operation in mathematical units of computation is referred to as asymptotic analysis.

The time required by an algorithm is typically classified into three types:

• Best Case – In the best-case scenario, the time required for program execution is minimal.
• Average Case – The average time required for program execution.
• Worst Case -Maximum time required for program execution in the worst-case scenario.

The following are some common asymptotic notations for calculating an algorithm’s running time complexity.

• O Notation

• Ω Notation
• θ Notation

• Big Oh Notation, O — The formal way to express the upper bound of an algorithm’s running time is with the notation O(n). It calculates the worst-case time complexity, or the longest time an algorithm can take to complete.

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₀. }

• Omega Notation, Ω — The formal way to express the lower bound of an algorithm’s running time is with the notation Ω (n). It calculates the best-case time complexity or the shortest amount of time an algorithm can take to complete.

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

• Theta Notation, θ — The notation (n) is used to express both the lower and upper bounds of an algorithm’s running time. It is written as follows:

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

Common Asymptotic Symptoms

constant	−	Ο(1)
logarithmic	−	Ο(log n)
linear	−	Ο(n)
n log n	−	Ο(n log n)
quadratic	−	Ο(n2)
cubic	−	Ο(n3)
polynomial	−	nΟ(1)
exponential	−	2Ο(n)