CODEWITHSUNDEEP
algorithmbig-o
doctopus
doctopus

Reputation: 5647

Big O for this triple nested loop?

What's the big O of this?

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++) {
                // Simple computation
            }
        }
    }
}

Can't really figure it out. Inclined to say O(n^4 log(n)) but feel like i'm wrong here.

Upvotes: 1

Views: 324

Answers (2)

yuvgin
yuvgin

Reputation: 1362

This is quite a confusing analysis, so let's break it down bit by bit to make sense of the calculations:

The outermost loop runs for n-1 iterations (since 1 ≤ i < n).
The next loop inside it makes (i² - 1) iterations for each index i of the outer loop (since 1 ≤ j < i²).

In total, this means the number of iterations for these two loops is equal to calculating the sum of (i²-1) for each 1 ≤ i < n. This is similar to computing the sum of the first n squares, and is order of magnitude of O(n³). Note the modulo operator % takes constant time (O(1)) to compute, therefore checking the condition if (j % i == 0) for all iterations of these two loops will not affect the O(n³) runtime.

Now let's talk about the inner loop inside the conditional.
We are interested in seeing how many times (and for which values of j) this if condition evaluates to true, since this would dictate how many iterations the innermost loop will run. Practically speaking, (j % i) will never equal 0 if j < i, so the second loop could actually be shortened to start from i rather than from 1, however this will not impact the Big-O upper bound of the algorithm.
Notice that for a given number i, (j % i == 0) if and only if i is a divisor of j. Since our range is (1 ≤ j < i²), there will be a total of (i-1) values of j for which this will be true, for any given i.
If this is confusing, consider this example:

Let's assume i = 4. Then our index j would iterate through all values 1,..,15=i², and (j%i == 0) would be true for j = 4, 8, 12 - exactly (i - 1) values. The innermost loop would therefore make a total of (12 + 8 + 4 = 24) iterations.
Thus for a general index i, we would look for the sum: i + 2i + 3i + ... + (i-1)i to indicate the number of iterations the innermost loop would make.

And this could be generalized by calculating the sum of this arithmetic progression. The first value is i and the last value is (i-1)i, which results in a sum of (i³ - i²)/2 iterations of the k loop for every value of i. In turn, the sum of this for all values of i could be computed by calculating the sum of cubes and the sum of squares - for a total runtime of O(n⁴) iterations of the innermost loop (the k loop) for all values of i.

Thus in total, the runtime of this algorithm would be the total of both runtimes we calculated above. We checked the if statement O(n³) times and the innermost loop ran for O(n⁴), so assuming // Simple computation runs in constant time, our total runtime would come down to:

O(n³) + O(n⁴)*O(1) = O(n⁴)

Upvotes: 2

P.Gupta
P.Gupta

Reputation: 575

Let us assume that i = 2.Then j can be [1,2,3].The "k" loop will run for j = 2 only. Similarly for i=3,j can be[1,2,3,4,5,6,7,8].hence, k can run for j = 3,6. You can see a pattern here that for any value of i, the 'k' loop will run (i-1) times.The length of loops will be [i,2*i,3*i,....i*i].

Hence the time complexity of k loop is

=i+(2*i)+(3*i)+ ..... +(i*i)

=(i^2)(i+1)/2

Hence the final complexity will be

= (n^3)(n+3)/2

Upvotes: 0

Related Questions