Examples of Time Complexity2

Find out some examples based on Time Complexity

1 November, 2016     

main()
{
         int i, j, x;
         x = x+1;
         for(i=1; i<=n;i++)
         x = x+1;

        for(i=1; i<=n;i++)
         for(j=1; j<=n;j++)
         x = x+1;
}

Solution:       Statement      =   4
                       Execution       =   4
                        Complexity    =   O(n2)
                        Exp:  There is four statement which is going to be execute every time so time complexity is O(n2).
                                  1 + 1+ n + n2    
NOTE: All lower term will discard so the complexity is O(n2) . ALL ARE IN POWER OF n.

main()
          {
              Int i,n;
              i=n;

         while(i>1)
               {
                        x=x+1;
                         i=i/2;
                }        
          }

Solution:       Statement      =   2
                       Execution        =  2
                       Complexity     =  O(n3)
                       Exp:  There is two statement which is going to be execute every time so time complexity is O(n3).
                        1 + n* n * n/2      =     1+ n3/2
              

               All lower term will discard so the complexity is O(n3).
               In depth if we execute for the first time one loop will go n times ,
               another for n times and another for n/2 so time complexity for the first
                time iteration is multiple of this and addition of first statement.

function (int n) {
              If(n == 1) return;
              for(int i=1 ; i<= n ; i++)
     {
             for(int j=1; j<=n; j++)
              printf(“”);
               break
      }
}

Solution:
                       Statement    = 1
                       Execution     = 1
                       Complexity   = n
        The complexity of the function is O(n).
         Even though the inner loop is bounded by n , but due to the break statement it is executing only once.