Time Complexity when Loop Variable Depends upon Outer Loop Variable

Question

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.

Answer 1

While the end result is correct, I wouldn't accept what is written in the question as an answer, because I can't really see how it gets to the answer.

The innermost loop: There are two cases. If j % i ≠ 0 then it iterates once, if j % i = 0 then it iterates j times.

The middle loop: Given i, it iterates i^2 times. The value of j will range from 1 to i^2. There are i cases j = i, j = 2i, j = 3i, ..., j = i^2 where j % i = 0, and i^2 - i cases where j % i ≠ 0. The inner loop will iterate once (i^2 - i) times. The inner loop will iterate j times when j = i, j = 2i, j = 3i, ..., j = i^2. The total number of iterations is the sum of (t * i) for 1 ≤ t ≤ i, which is i * (i - 1)/2 * i which is about i^3 / 2. The other cases only involved i^2 - i operations and can therefore be ignored. Summary: Given i, the middle loop performs about i^3 / 2 operations.

The outer loop: i ranges from 1 to n. There are i^3 / 2 operations for each iteration. So the total number of operations is the sum of (i^3 / 2) for i = 1 to n, which is about i^4 / 8.