What is asymptotic notation? 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 notation 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.

fig-1 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.

fig-1 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.

Fig-1 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.