SEMESTER 1ST AND 2ND (1ST YEAR) – PROGRAMMING WITH "C" (2418101)

 ASYMPTOTIC NOTATION: -

             When it comes to analysis the complexity of an algorithm in the terms of time and space, we cannot provide an exact or perfect time required and space required by an algorithm. Therefore we express it using some standard notations, which is also known as asymptotic notation.

It refers to computing the running time of any operation in mathematical unit of computation.

Time required by an algorithm falls under three types: -

a.   Worst case: -

When the time taken by any program execution is maximum, termed as worst case

b.   Best case: -

When the time taken by any program execution is minimum, termed as best case

c.    Average case: -

When the time taken by any program execution is average, termed as average case

There is some commonly used asymptotic notation which is used to calculate time complexity of an algorithm: -

                a.      O notation (Big Oh notation)

                b.           Ω notation (Omega notation)

                c.         θ notation (Theta notation)

 

1.   Big Oh notation: -

1.   Big Oh notation O(n)  is the formal way to express the upper bound of an algorithm’s running time.

2.   It can be also called as upper bound notation.

3.   It measures the worst case time complexity or the worst amount of time that can be taken by an algorithm.

4.  For a function f(n)

 f(n) = O (g (n)) there exists c > 0 and n0 

such that f(n) ≤ c.g(n) for all n > n0. }

 Example (linear equation): -

f(n)= 3n + 2, when n is at least 2

3n + 2 <= 3n + n <= 4n, so f(n) = O (n)

 

2.   Omega notation: -

1.   Omega notation  is the formal way to express the lower bound of an algorithm’s running time.

2.   It can be also called as lower bound notation.

3.   It measures the best case time complexity or the best amount of time that can be taken by an algorithm.

4.   For a function f(n)

 (f(n)) = Ω g(n) :  there exists c > 0 and n₀ such that g(n) ≤ c.f(n) for all n > n₀. }

 

Example (linear equation): -

f(n)= 3n + 2 > 3n for all n, so f(n)=  Ω(n).  Also f(n) = 3n + 3 > 3n and so   (f(n)) = Ω g(n).

3.   Theta notation: -

1.     Theta notation  is the formal way to express average bound (i.e. both lower case and upper case) of an algorithm’s running time.

2.     It can be also termed as average bound notation.

3.     It measures the average case time complexity or the average amount of time that can be taken by an algorithm.

4.     For a function f(n)

          (f(n)) = θ g(n) if and only if g(n) =  Ο(f(n))

 and g(n) = Ω(f(n)) for all n > n0. }

 

( Below two points comes under complexity measure in terms of time and space )

Time complexity: -

1.   Algorithm which signifies the total time required by the program to run till its completion termed as time complexity.

2.   The time complexity algorithm is most commonly expressed by using big Oh notation (we have already know about Big Oh notation).

3.   The most commonly estimated by counting the number of elementary steps performed by any algorithm to finish execution, it is done by time complexity.

4.   Let’s take an example :-

Find square of a number a

for i= 1 to a

 do a= a+a; /*when loops end “a” will hold its square*/

return a;

           As we can see, loop will execute “a” numbers of time, so the time complexity of the above program is at least “a” number of times.

5.   Let’s take another example: -

   Find square of a number b

return b*b;

    In the above example time complexity will be constant, because it will not depend on the value of b. It will always give the result in one-step.