Time complexity O(N) of nested loops with if-statement: O(N^4)?

Question

I am trying to figure out a tight bound in terms of big-O for this snippet:

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++;
        }
    }
}

If we start with the inner most loop, it will in worst case run k = n^2 times, which accounts for O(N^2). The if-statement will be true every time j = m*i, where m is an arbitrary constant. Since j runs from 1 to i^2, this will happen when m= {1, 2, ..., i}, which means it will be true i times, and i can at most be n, so the worst case will be m={1,2, ..., n} = n times. The second loop should have a worsts case of O(N^2) if i = n. The outer loop has a worst case complexity of O(N).

I argue that this will combine in the following way: O(N^2) for the inner loop * O(N^2) for the second loop * O(N) for the outer loop gives a worst case time complexity of O(N^5)

However, the if-statement guarantees that we will only reach the inner loop n times, not n^2. But regardless of this, we still need to go through the outer loops n * n^2 times. Does the if-test influence the worst case time complexity for the snippet?

Edit: Corrected for j to i^2, not i.

Answer 1

You can simplify the analysis by rewriting your loops without an if, as follows:

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

This eliminates steps in which the conditional skips over the "payload" of the loop. The complexity of this equivalent system of loops is O(n⁴).