Why is the computational complexity O(n^4)?

Let’s label the loops A, B and C:

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

• Loop A iterates O(n) times.
• Loop B iterates O(i²) times per iteration of A. For each of these iterations:
  • j % i == 0 is evaluated, which takes O(1) time.
  • On 1/i of these iterations, loop C iterates j times, doing O(1) work per iteration. Since j is O(i²) on average, and this is only done for 1/i iterations of loop B, the average cost is O(i² / i) = O(i).

Multiplying all of this together, we get O(n × i² × (1 + i)) = O(n × i³). Since i is on average O(n), this is O(n⁴).

The tricky part of this is saying that the if condition is only true 1/i of the time:

Basically, why can’t j % i go up to i * i rather than i?

In fact, j does go up to j < i * i, not just up to j < i. But the condition j % i == 0 is true if and only if j is a multiple of i.

The multiples of i within the range are i, 2*i, 3*i, …, (i-1) * i. There are i - 1 of these, so loop C is reached i - 1 times despite loop B iterating i * i - 1 times.