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.

• The first loop consumes n iterations.
• The second loop consumes n*n iterations. Imagine the case when i=n, then j=n*n.
• The third loop consumes n iterations because it's executed only i times, where i is bounded to n in the worst case.

Thus, the code complexity is O(n×n×n×n).

I hope this helps you understand.