Types of Algorithm and Its Complexity Analysis

In this post, we will learn types of Algorithm and its time complexity analysis with examples

 An algorithm is divided into two forms called iterative and recursive, as shown above. Firstly, we analyze the time complexity of the iterative algorithm and then recursive.

Example 1:

                          A()

                          {

                           int i;

                           for(i=1 to n)   % loop run n times

                           pf("deepa");

                          }

First, the above function is fall into the independent category. Hence, the running time of the loop will be n and it print the particular name n times. Therefore, the worst case time complexity of this algorithm will be O(n).

Example 2:
                        A()
                        {
                        int i;
                        for(i=1, i^2<=n, i++)
                        printf("deepa");
                        }
Similarly, the loop run  √n times. Hence, the time complexity of this algorithm can be defined using three notations. Because, in all the cases the time complexity will be remain same.

O(√n) = = 𝛀√n = = 𝜭√n

 Example 3:
                      A()
                      {
                      int i;
                      for(i=1 to n)   % loop runs n times
                      for(j=1 to n)   % loop runs n times
                      printf("deepa");
                      }
Loops are independent, therefore the time complexity will be the multiplication of the loops O(n^2).

Example 4:
                     A()
                     {
                      int i,j,k;
                      for(i=1; i<=n; i++)
                      { 
                      for(j=1; j<=i; j++)
                      {
                      for(k=1;k<=100;k++)                 k= 1t x 100    2t x 100    3t x 100........ nt x 100
                      {
                      printf("deepa");                        = (1x100+2x100+3x300+.......................nx100)
                      }                                                   = 100( 1+2+3+................................................n)
                      }                                                   = 100 x n(n+1)/2
                      }                      Time complexity = O(n^2)
This problem is dependent because the second loop is depend on the value of first loop. Therefor, we have to unroll the loop and consider the final loop series for calculation of time complexity.

Example 5:
                      A()
                      {
                      int i,j,k,n
                      for(i=1; i<=n;i++)
                      {
                      for(j=1; j<=i^2;j++)        j=1t              4t              9t.........................nt^2

                      {
                      for(k=1;k<=n/2;k++)      k=1t x n/2    4t x n/2     9txn/2..............+ nt x n/2
                      {
                       printf("deepa")              = n/2(1+4+9+..........................................+n^2)
                       }                                       =  n/2 (n(n+1)(2n+1)/6)
                       }                                       = O(n^4)
                       }

 This problem is dependent because the  second loop is depend on the value of first loop.
Example 6:
                   A()
                   {
                   for(i=1;i<=n,i=i*2)               i= 1        2       4       8..............k
                   pf("deepa");                       i= 2^0   2^1   2^2   2^3.........2^k
                   }
In this problem, the increment of i is not sequential. Hence, we assume the loop will end after k iteration.  In terms of n, the loop will be end when the i value will be greater than or equal to n
Hence,
2^k=n
Take log both the side...
k=log2(n)
Time complexity will be=O(log2(n))
Example 7:
                    A()
                    {
                     int i,j,k,n
                     for(i=n/2;i<=n,i++)
                     {
                     for(j=1; j<=n/2; j++)
                     {
                     for(k=1,k<=n;k=k*2) % loop runs log2(n) times
                     {
                      pf("deepa")
                     } 
The above problem is independent. Hence, the multiplication of the loops gives the complexity.
= n/2 x n/2 x log2(n)
= O(n^2log2(n))
Example 8:
                     A()
                     {
                     int i,j,k;
                     for(n/2;i<=n; i++)                % loop runs n/2 times
                     {
                     for(j=1; j<=n; j=j*2)            % loop runs log2(n) times
                     {
                     for(k=1; k<=n;k=k*2)         % loop runs log2(n) times
                     {
                     pf("deepa");
                     }
                     }
                     }
                     }
Similarly, this problem is also independent. Hence, the time complexity will be
= n/2xlog2(n)xlog2(n)
= O(n*log2n*log2n)

In the next post, we will see the complexity analysis of recursive algorithm....

Till try few example....

What is time complexity in Big-O

• A()

          {
          for(int i=1;i<=n;i++)
          {
          for(int j=1; j<=n; j++)
          {
          printf("*");
          break;
          }
          }
          }

• A()

          {
          int count=0;
          for(int i=n/2; i<=n; i++)
          for(int j=1;j+n/2<=n;j++)
          for(int k=1,k<=n;k=k*2)
          count++;
          }