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

Question

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

I don't understand how when j = i, 2i, 3i... the last for loop runs n times. I guess I just don't understand how we came to that conclusion based on the if statement.

Edit: I know how to compute the complexity for all the loops except for why the last loop executes i times based on the mod operator... I just don't see how it's i. Basically, why can't j % i go up to i * i rather than i?

Answer 1

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.

Answer 2

• 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.