Asymptotic Notations – Big O, θ, Ω and ω

The term Asymptote means a line whose distance to a given curve tends to be zero. An Asymptotic may or may not intersect its associated curve. There are mainly five types of Asymptotic notations given as follows:

Big O Notation:

The function f(n)=O(g(n)) if f(n)≤c*g(n) for all n, n≥n0 where c and n0 are positive constants. The function g(n) indicates the upper bound of f(n) and so, g(n) should be small as possible for which the statement f(n)=O(g(n)) is true.

Theta Notation:

The function f(n)=θ(g(n)) if c1*g(n)≤ f(n)≤ c2*g(n) for all n, n≥n0 where c1, c2 and n0 are positive constants. The function g(n) is a tight bound of f(n) because g(n) is both upper and lower bound on f(n).

Omega Ω Notation:

The function f(n)=Ω(g(n)) if f(n)≥c*g(n) for all n, n≥n0 where c and n0 are positive constants. The function g(n) is only a lower bound of f(n) and so, g(n) should be as large as possible for which the statement f(n)≥c*g(n) is true.

Little Omega ω Notation:

The function f(n)=ω(g(n)) (read as f of n is little omega of g of n)

Little o Notation:

The function f(n)=o(g(n)) (read as f of n is little o of g of n)