CODEWITHSUNDEEP
algorithmbig-o
doctopus
doctopus

Reputation: 5657

What's the big O for this triple nested loop?

Outer loop is O(n), 2nd loop is O(n^2) and 3rd loop is also O(n^2), but the 3rd loop is conditional.

Does that mean the 3rd loop only happens 1/n (1 every n) times and therefore total big O is O(n^4)?

   for (int i = 1; i < n; i++) {
        for (int j = 1; j < (n*n); j++) {
            if (j % i == 0) {
                for (int k = 1; k < (n*n); k++) {
                    // Simple computation
                }
            }
        }
    }

Upvotes: 2

Views: 468

Answers (1)

ruakh
ruakh

Reputation: 183602

For any given value of i between 1 and n, the complexity of this part:

    for (int j = 1; j < (n*n); j++) {
        if (j % i == 0) {
            for (int k = 1; k < (n*n); k++) {
                // Simple computation
            }
        }
    }

is O(n4/i), because the if-condition is true one ith of the time. (Note: if i could be larger than n, then we'd need to write O(n4/i + n2) to include the cost of the loop iterations where the if-condition was false; but since i is known to be small enough that n4/i ≥ n2, we don't need to worry about that.)

So the total complexity of your code, adding together the different loop iterations across all values of i, is O(n4/1 + n4/2 + n4/3 + ⋯ + n4/n) = O(n4 · (1/1 + 1/2 + 1/3 + ⋯ + 1/n)) = O(n4 log n).

(That last bit relies on the fact that, since ln(n) is the integral of 1/x from 1 to n, and 1/x is decreasing over that interval, we have ln(n) < ln(n+1) < (1/1 + 1/2 + 1/3 + ⋯ + 1/n) < 1 + ln(n).)

Upvotes: 3

Related Questions