How to calculate time complexity of three nested dependent loops?

Question

Consider the code:

void foo(int n){
    int s = 0;
    for (i=1; i<=n; i++)
        for(j=1;j<=i*i;j++)
            if (j % i == 0){
                for (k=1; k<=j; k++)
                    s++;
            }
}

How would we calculate the time complexity of the above snippet having three nested dependent loops ?

I think i will run till n, j till i² or n², k till j or n².

So time complexity should be O(n*n²*n²) or, O(n⁵) according to me. But I know its O(n⁴). Where am I wrong?

Answer 1

This line: if (j % i == 0) is making the difference. for eg, for i=3 , j will run 9 times.

and (j % i == 0) will be true only 3 times. hence , the k loop will not run for 9 times but only 3 times.