Aysymtotic notation

The Word Asymptotic means approaching to value or curve (as some sort of limit is taken).

It consist of function f(n) and g(n) which is nonnegative

There are five asymptotic notation as

• Ο notation (big Ο notation) :- It is asymptotical upper bound notation.

The function  (f(n))= Ο( g(n)) if and only if  there exists positive constant c and n0 such that f(n)  ≤ c*(g(n)) for all values of n, n ≥ n₀ 

In give figure consist of X axis as number of inputs and Y- axis consist of time or space required.

The function c*g(n) is less or equal as compare to f(n) up to n₀ ^th  point after

n₀ ^th point the value of c*g (n) is always greater and f(n) is always less than c*g(n) function.

After n₀ ^th point the two function never collied or f(n) is not greater than c*g(n) Example

            3n+2= Ο (n) as

             3n+2 is function f(n) we need to find out c*g(n) function as O(n)

Step 1:- Find greater function than 3n+2  i.e greater function is 4n (by increasing constant value)

               3n+2 ≤  4*n             as  C*g(n)  is  4*n

Step 2: -     Put n=1;      3(1)+2 ≤ 4(1)   =>       5 ≤ 4  ….?

                   put n=2;         3(2)+2≤ 4(2)  =>         5 ≤ 8

                  put n=3;         3(3)+2≤ 4(3) =>          8≤ 12   value of n₀=2

after input value 2 i.e n0 value 4n is always greater than 3n+2

      

• ʘ notation(Theta notation):- It is asymptotical tight bound

The function f(n)= ʘ(g(n))  if and only if  there exists positive constant c and n₀ such that c₁g(n) ≤  f(n)  ≤ c₂*(g(n)) for all values of n, n ≥ n₀ 

The function c1*g(n) is less or equal as compare to f(n). The f(n) is again less or equal to c₂g(n) up to n₀ ^th  point after n₀ ^th point the value of c₂*g (n) is always greater and f(n) is greater than c₁*g(n) function. F(n) is in between(sandwiched) c₁*g(n) and c₂*g(n).

After n₀ ^th point the three function never collied or ) c₁*g(n)  is f(n) is not

  Figur 2:- f(n)=ʘ(n)[/caption]greater than c₂*g(n) Example

3n+2= ʘ (n) as

3n+2 is function f(n) we need to find out c₂*g(n) function as ʘ(n)

Step 1:- Find greater function than 3n+2  i.e greater function is 4n (by increasing constant valu 3n+2 ≤  4*n             as  C₂*g(n)  is  4*n

Step 2: -  Put n=1;      3(1)+ 2 ≤ 4(1)   =>      5 ≤ 4  ….?

     put n=2;         3(2)+2≤ 4(2)  =>         5 ≤ 8

      put n=3;         3(3)+2≤ 4(3) =>          8≤ 12   value of n₀=2

step 3:-     2n≤3n+2      as  C₁*g(n) is 2n

       put n=1  2(1)≤ 3(1)+2       =>     2≤ 5

      i.e     2n≤ 3n+2≤4n similar to  c₁g(n) ≤  f(n)  ≤ c₂*(g(n))

     after input value  n₀=1 the function satisfy the condition

 

  ʘ notation(Theta notation):- It is asymptotical tight bound.The function f(n)= ʘ(g(n))  if and only if  there exists positive constant c and n₀ such that c₁g(n) ≤  f(n)  ≤ c₂*(g(n)) for all values of n,  n ≥ n₀ 

The function c₁*g(n) is less or equal as compare to f(n). The f(n) is again less or equal to c₂g(n) up to n₀ ^th  point after n₀ ^th point the value of c₂*g (n) is always greater and f(n) is greater than c₁*g(n) function. The f(n) is sandwiched sandwitched c₁*g(n) and c₂*g(n).

After n₀ ^th point the three function never collied or ) c₁*g(n)  is not greater than  f(n) and f(n) is not greater than c₂*g(n) Example

                 3n+2 is function f(n) we need to find out c*g(n) function as O(n)

Step 1:- Find greater function than 3n+2  i.e greater function is 2n (by decreasing constant value)

                    2nn  ≤3n+2  as  C*g(n)  is  2*n

Step 2: -  Put n=1;     2(1) ≤ 3(1)+2   =>       2 ≤ 4  ….?

after input value 1 the functions is satisfying given condition

•