Post Reopened by enderland, gnat, Bart van Ingen Schenau, JB King

occurred Nov 9, 2015 at 20:56

formatting, spelling and grammar cleanup

Source Link

edit approved Nov 9, 2015 at 17:46

281
5
8

Time Complexity when loop variable dependLoop Variable Depends upon outer loop variableOuter Loop Variable

What is the time complexity of the following piece of code in worst case?

s=0;s = 0;
for(i=1;i<=n;++i){

 i = for(j=1;j<=i*i;j++1; i <= n; ++i ) {
     for( j = 1; j <= i * 
 i; j++ ) {
    for(k=1;k<=j and j%i==0;k++)  for( k = /*1; k k<=j<= j and j%i==0j */
% i == 0; k++ )
      s++;
      s++;
    }
}

Each loop depend on the outer loop variable.How to How should I proceed in such a case? Innermost

The innermost loop will run only sometimes.How tooccasionally, so how can I evaluate this case?

For every increment of ii middle loop runs for i^2i^2 times and for. For every iteration of middle loop, i mI'm not able to calculate how many times the innermost loop will run in terms of the outer loop.

I think innermost loop iterates for ii times. MiddleThe middle loop runruns for j=1 to i^2j = 1 to i^2 and j%i!=0j % i != 0 is in ii cases and for other ii cases j%i=0, j % i = 0. As inner loop runruns for j%i==0j % i == 0 it would be iterated ii times.
Now as

Now for the times the innermost loop run for iruns i times,middle the middle loop run for i^2runs i^2 times and the outer loop run for i timesruns i times, I think the complexity would be n^4is n^4.

Time Complexity when loop variable depend upon outer loop variable

What is the time complexity of the following piece of code in worst case?

s=0; 
for(i=1;i<=n;++i){

   for(j=1;j<=i*i;j++){
             
        for(k=1;k<=j and j%i==0;k++)     /*  k<=j  and j%i==0 */
           s++;
      
   }
}

Each loop depend on the outer loop variable.How to proceed in such case? Innermost loop will run only sometimes.How to evaluate this case?

For every increment of i middle loop runs for i^2 times and for every iteration of middle loop, i m not able to calculate how many times innermost loop will run in terms of outer loop.

I think innermost loop iterates for i times. Middle loop run for j=1 to i^2 and j%i!=0 is in i cases and for other i cases j%i=0. As inner loop run for j%i==0 it would be iterated i times.
Now as innermost loop run for i times,middle loop run for i^2 times and outer loop run for i times , I think complexity would be n^4

Time Complexity when Loop Variable Depends upon Outer Loop Variable

What is the time complexity of the following piece of code in worst case?

s = 0;
for( i = 1; i <= n; ++i ) {
    for( j = 1; j <= i * i; j++ ) {
        for( k = 1; k <= j and j % i == 0; k++ )
            s++;
    }
}

Each loop depend on the outer loop variable. How should I proceed in such a case?

The innermost loop will run only occasionally, so how can I evaluate this case?

For every increment of i middle loop runs i^2 times. For every iteration of middle loop, I'm not able to calculate how many times the innermost loop will run in terms of the outer loop.

I think innermost loop iterates for i times. The middle loop runs for j = 1 to i^2 and j % i != 0 is in i cases and for other i cases, j % i = 0. As inner loop runs for j % i == 0 it would be iterated i times.

Now for the times the innermost loop runs i times, the middle loop runs i^2 times and the outer loop runs i times, I think the complexity is n^4.

added 330 characters in body

Source Link

edited Oct 27, 2015 at 4:55

Ashish Pani

133
4

What is the time complexity of the following piece of code in worst case?

s=0; 
for(i=1;i<=n;++i){

   for(j=1;j<=i*i;j++){
             
       for(k=1;k<=j and j%i==0;k++)     /*  k<=j  and j%i==0 */
           s++;
      
   }
}

Each loop depend on the outer loop variable.How to proceed in such case? Innermost loop will run only sometimes.How to evaluate this case?

For every increment of i middle loop runs for i^2 times and for every iteration of middle loop, i m not able to calculate how many times innermost loop will run in terms of outer loop.

I think innermost loop iterates for i times. Middle loop run for j=1 to i^2 and j%i!=0 is in i cases and for other i cases j%i=0. As inner loop run for j%i==0 it would be iterated i times.
Now as innermost loop run for i times,middle loop run for i^2 times and outer loop run for i times , I think complexity would be n^4

What is the time complexity of the following piece of code in worst case?

s=0; 
for(i=1;i<=n;++i){

   for(j=1;j<=i*i;j++){
             
       for(k=1;k<=j and j%i==0;k++)     /*  k<=j  and j%i==0 */
           s++;
      
   }
}

Each loop depend on the outer loop variable.How to proceed in such case? Innermost loop will run only sometimes.How to evaluate this case?

For every increment of i middle loop runs for i^2 times and for every iteration of middle loop, i m not able to calculate how many times innermost loop will run in terms of outer loop.

What is the time complexity of the following piece of code in worst case?

s=0; 
for(i=1;i<=n;++i){

   for(j=1;j<=i*i;j++){
             
       for(k=1;k<=j and j%i==0;k++)     /*  k<=j  and j%i==0 */
           s++;
      
   }
}

Each loop depend on the outer loop variable.How to proceed in such case? Innermost loop will run only sometimes.How to evaluate this case?

For every increment of i middle loop runs for i^2 times and for every iteration of middle loop, i m not able to calculate how many times innermost loop will run in terms of outer loop.

I think innermost loop iterates for i times. Middle loop run for j=1 to i^2 and j%i!=0 is in i cases and for other i cases j%i=0. As inner loop run for j%i==0 it would be iterated i times.
Now as innermost loop run for i times,middle loop run for i^2 times and outer loop run for i times , I think complexity would be n^4

edited title

Link

edited Oct 27, 2015 at 4:34

Ashish Pani

133
4

Time Complexity of following codewhen loop variable depend upon outer loop variable

deleted 32 characters in body

Source Link

edited Oct 26, 2015 at 19:16

Ashish Pani

133
4

Loading

added 188 characters in body

Source Link

edited Oct 26, 2015 at 19:07

Ashish Pani

133
4

Loading

Post Closed as "Duplicate" by CommunityBot, Bart van Ingen Schenau, MetaFight

Big-O for nested loop

occurred Oct 26, 2015 at 19:06

deleted 33 characters in body

Source Link

edited Oct 26, 2015 at 18:53

Ashish Pani

133
4

Loading

corrected code

Source Link

edited Oct 26, 2015 at 18:12

Ashish Pani

133
4

Loading

Source Link

asked Oct 26, 2015 at 18:03

Ashish Pani

133
4

Loading

Stack Exchange Network

Return to Question

Time Complexity when loop variable dependLoop Variable Depends upon outer loop variableOuter Loop Variable

Time Complexity when loop variable depend upon outer loop variable

Time Complexity when Loop Variable Depends upon Outer Loop Variable

Time Complexity of following codewhen loop variable depend upon outer loop variable