Asymptotic Notations

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

• Ο Notation (Wast Case)

• Ω Notation (Best Case)

• θ Notation (Average Case)

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.

For example, for a function f(n)

Ο(f(n)) = { g(n) : there exists c $\gt$; 0 and $n_{0}$ such that f(n) ≤ c.g(n) for all n $\gt$; n 0 . }

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.

For example, for a function f(n)

Ω(f(n)) ≥ { g(n) : there exists c $\gt$; 0 and n$_{0}$ such that g(n) ≤ c.f(n) for all n $\gt$; n 0 . }

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. It is represented as follows −

θ(f(n)) = { g(n) if and only if g(n) = Ο(f(n)) and g(n) = Ω(f(n)) for all