0

i have to analyse this code's complexity but i'm very comfused with the condition of IF.

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

If the "(j%i==0)" if-condition was not there i would be able to compute the complexity but i cant understand it. I need some explanation about how we can compute how many times this condition will be true.

Thank you.

DIMITRIOS
  • 305
  • 1
  • 3
  • 10
  • For a give i and j, the condition will be true j/i times. Is that enough of a hint? – Beta Jun 03 '17 at 14:51

1 Answers1

0

The complexity of the algorithm would be O(n^3), because of the 3 for statements.

You can have a look at if statement - how does IF affect complexity

where there is a nice link on more information.

Alexios Tsiaparas
  • 880
  • 10
  • 17