Question

What is the time complexity of the following code? (in big-O notaion)

sum = 0

var = 0

product = 0

for i = 1 to (n+2){

sum = sum + 2i

for j = i to [(n*n)+i]{

var = sum + var

for k = sum + var{

product = var++

}

}

}

for m + 1 to (j*i){

sum = sum + product

}

Answer 1

Big O notation is a basically mathematical notation by which we can show or see analysis of run time of a code or program in processor and memory of system.

in other word we can say that in Big O notation O stand for growth of an algorithm. Big O notation describes the limiting behavior of a function also the big O notation defines an upper bound of an algorithm for example lets take time whole time complexity of an algoritm like:

O(1) + (n)

so in big O notation we take only O(n) because O(n) is greater than O(1). this is the meaning of Big O notation or we can say it is arthematic rule of Big O notaion.

function of Big O notation is writing as

O(f(x))

where f(x) = function of time complexity of program

lets take time complexity of a program is O(n)

so, O(f(x)) = f(x)

where f(x) = n

now time complexity of our program:

sum =0;   // here it is a constant so its complexity will be O(1) or it will run at 1 time only

var=0 ; // here also O(1)

product =0 // also here O(1)

for (i =1; i <n+2; i++)

{

      sum= sum+ 2i;       // for this first for loop time complexity will be O(n)

       for( j=i; i< [(n*n) +i] ; j++)

       {

              var =sum+var;    // for this second loop time complexity will be O(n) also. but if we multiply the variable then here time complexity will be in logn but here in program constant part is multiplying

               for(k= sum+var)

                {

                      product = var++; // now for the third loop time complexity will be O(n) also

                  }

         }

}

for(m+1; j<i)

{

   sum= sum + product;   // here for this loop time complexity will be O(n)

}

so, we have these complexity all over and we will add all the complexity now:

= O(1) + O(1) + O(1) + [ O(n) * O(n) * O(n) ] + O(n)

=O(n^3)    // by the big O notation arthematic rule we have to take big value and leave the rest

so for this program time complexity in Big O notation will be O(n^3).