Time complexity of following code

Question

I want to find the time complexity of the following code but I'm not sure if I am doing it right. Printf is the basic process.Is time complexity of printf changing due to i*j or i*k?

i=0;              //c1
while (i<n){      //c2*(n+1)
     for(j=i; j<n; j++)  // c3*n*(n+1)
         printf("The product of %d and %d is %d\n",i,j,i*j);   //c4*n*n
     for(k=n; k>i; k--)    //c5*n*(n-1)
         printf("The product of %d and %d is %d\n",i,k,i*k);   //c6*n*n
      i++;  //c7*n 
}

so the time complexity= c1+c2*(n+1)+c3*(n^2 +n)+c4*n^2 + c5*(n^2 -n)+c6*n^2 +c7*n=c8*n^2 +c9*n +c10

score 1 · Answer 1 · answered Sep 17 '17 at 13:36

To find the time complexity of your code,

    i=0;
    while (i<n){      // a loop will run n times
            for(j=i; j<n; j++)  // a loop will run n - i times
                     printf("The product of %d and %d is %d\n",i,j,i*j);  
            for(k=n; k>i; k--)    //a loop will run n -i times
                     printf("The product of %d and %d is %d\n",i,k,i*k);
            i++;
    }

So the total is about n * ((n-i) + (n -i)). But we only need to care about the term increases fastest when n goes to infinity. So it is O(n^2).

Time complexity of following code

1 Answers1