Describe different types of asymptotic notation with example

Asymptotic Notation: Asymptotic notation are used to describe the asymptotic running time of an algorithm that are defined in terms of functions whose domains are the set of natural numbers  N = {0, 1, 2, …}.

Such notations are convenience for describing the worst case running time function T(n), which is usually defined only on an integer input size.

Asymptotic Notations are three types, these are –

(i) Big-O Notation

(ii) Omega-Ω Notation

(iii) Theta-  Notation

(i) Big- O Notation:- The function f(n)= O(g(n)), if there exist positive constants C and n₀ such that f(n) ≤ c* g(n) for all n, n ≥ n­₀. We used O-notation to give an upper bound on a function to within a constant factor.

  

  

Figure shows the intuition behind big O- notation for all values n to the right of n₀, the value of the function f(n) is on or below g(n).

Example of O:   

3n+2= O(n), since 3n+2 ≤ 4n, for all n ≥ 2.

(ii) Ω (Omega) Notation: The function f(n) = Ω (g(n)) if there exist positive constants c and n₀, such that f(n) ≥ c * g(n) for all n, n ≥ n₀. We use Ω notation to give a lower bound on a function within a constant factor.

Figure shows the intuition behind Ω notation for all values n to the right of n₀, the value of the function f(n) is on or above g(n).

Example of Ω:

          3n+2= Ω(n), since 3n+2n ≥ 3n, for all n ≥ 1.

(iii) θ (Theta) Notation: The function f(n) =  (g(n)) if there exists positive constants C₁, C₂, C₃ and n₀ such that 0≤ C₁ g(n) ≤ f(n) ≤ C₂ g(n), We use  notation to give a tight bound on a function within a constant factor.

Figure shows the in intuition behind  notation. For all values n to the right of n₀, the value of the function f(n) is at above c,g(n) and at or below c₂g(n).

Example of θ:

If f(n)= 3n+6 and g(n), then f(n) = (g(n), or 3n+6= (n), as can be seen by using C₁=3, C₂=4 and N=5.