Time complexity question 3 loops + if statement

Question

I have some trouble finding the time complexity of the code below. I figured that the if statement will run for approximately n times; however, I could not manage to describe it mathematically. Thanks in advance.

int sum = 0;

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

Answer 1

Outer loop

Well, it's clear that it's O(n) because i is bounded by n.

Inner loops

If we take a look at the second loop alone, then it looks as follows:

...
for (int j = 1 ; j < i*i; j++){
...

j is bounded by i*i or simply n^2.

However, the innermost loop won't be executed for every j, but only for js that are divisible by i because that's what the constraint j % i == 0 means. Since j ~ i*i, there will be only i cases, when the innermost loop is executed. So, the number of iterations in the inner loops is bounded by i^3 or simply n^3.

Result

Hence, the overall time complexity is O(n⁴).