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

O(n^4) is polynomial time complexity.

Answer 2

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 3

Remove if and modulo without changing the complexity

Here's the original method:

public static long f(int n) {
    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++;
                }
            }
        }
    }
    return sum;
}

If you're confused by the if and modulo, you can just refactor them away, with j jumping directly from i to 2*i to 3*i ... :

public static long f2(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j = i; j < i * i; j = j + i) {
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

To make it even easier to calculate the complexity, you can introduce an intermediary j2 variable, so that every loop variable is incremented by 1 at each iteration:

public static long f3(int n) {
    int sum = 0;
    for (int i = 1; i < n; i++) {
        for (int j2 = 1; j2 < i; j2++) {
            int j = j2 * i;
            for (int k = 0; k < j; k++) {
                sum++;
            }
        }
    }
    return sum;
}

You can use debugging or old-school System.out.println in order to check that i, j, k triplet is always the same in each method.

Closed form expression

As mentioned by others, you can use the fact that the sum of the first n integers is equal to n * (n+1) / 2 (see triangular numbers). If you use this simplification for every loop, you get :

public static long f4(int n) {
    return (n - 1) * n * (n - 2) * (3 * n - 1) / 24;
}

It is obviously not the same complexity as the original code but it does return the same values.

If you google the first terms, you can notice that 0 0 0 2 11 35 85 175 322 546 870 1320 1925 2717 3731 appear in "Stirling numbers of the first kind: s(n+2, n).", with two 0s added at the beginning. It means that sum is the Stirling number of the first kind s(n, n-2).

Answer 4

All the other answers are correct, I just want to amend the following. I wanted to see, if the reduction of executions of the inner k-loop was sufficient to reduce the actual complexity below O(n⁴). So I wrote the following:

for (int n = 1; n < 363; ++n) {
    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++;
                }
            }
        }
    }

    long cubic = (long) Math.pow(n, 3);
    long hypCubic = (long) Math.pow(n, 4);
    double relative = (double) (sum / (double) hypCubic);
    System.out.println("n = " + n + ": iterations = " + sum +
            ", n³ = " + cubic + ", n⁴ = " + hypCubic + ", rel = " + relative);
}

After executing this, it becomes obvious, that the complexity is in fact n⁴. The last lines of output look like this:

n = 356: iterations = 1989000035, n³ = 45118016, n⁴ = 16062013696, rel = 0.12383254507467704
n = 357: iterations = 2011495675, n³ = 45499293, n⁴ = 16243247601, rel = 0.12383580700180696
n = 358: iterations = 2034181597, n³ = 45882712, n⁴ = 16426010896, rel = 0.12383905075183874
n = 359: iterations = 2057058871, n³ = 46268279, n⁴ = 16610312161, rel = 0.12384227647628734
n = 360: iterations = 2080128570, n³ = 46656000, n⁴ = 16796160000, rel = 0.12384548432498857
n = 361: iterations = 2103391770, n³ = 47045881, n⁴ = 16983563041, rel = 0.12384867444612208
n = 362: iterations = 2126849550, n³ = 47437928, n⁴ = 17172529936, rel = 0.1238518469862343

What this shows is, that the actual relative difference between actual n⁴ and the complexity of this code segment is a factor asymptotic towards a value around 0.124... (actually 0.125). While it does not give us the exact value, we can deduce, the following:

Time complexity is n⁴/8 ~ f(n) where f is your function/method.

• The wikipedia-page on Big O notation states in the tables of 'Family of Bachmann–Landau notations' that the ~ defines the limit of the two operand sides is equal. Or:

  f is equal to g asymptotically

(I chose 363 as excluded upper bound, because n = 362 is the last value for which we get a sensible result. After that, we exceed the long-space and the relative value becomes negative.)

User kaya3 figured out the following:

The asymptotic constant is exactly 1/8 = 0.125, by the way; here's the exact formula via Wolfram Alpha.

Answer 5

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

Answer 6

Let's have a look at the first two loops.

The first one is simple, it's looping from 1 to n. The second one is more interesting. It goes from 1 to i squared. Let's see some examples:

e.g. n = 4    
i = 1  
j loops from 1 to 1^2  
i = 2  
j loops from 1 to 2^2  
i = 3  
j loops from 1 to 3^2  

In total, the i and j loops combined have 1^2 + 2^2 + 3^2.
There is a formula for the sum of first n squares, n * (n+1) * (2n + 1) / 6, which is roughly O(n^3).

You have one last k loop which loops from 0 to j if and only if j % i == 0. Since j goes from 1 to i^2, j % i == 0 is true for i times. Since the i loop iterates over n, you have one extra O(n).

So you have O(n^3) from i and j loops and another O(n) from k loop for a grand total of O(n^4)