Big Oh Notation and Calculating the Running Time for a Triple-Nested For-Loop

Question

In Computer Science, it is very important for Computer Scientists to know how to calculate the running times of algorithms in order to optimize code. For you Computer Scientists, I pose a question.

I understand that, in terms of n, a double-nested for-loop typically has a running time of n² and a triple-nested for-loop typically has a running time of n³.

However, for a case where the code looks like this, would the running time be n4?

x = 0;
for(a = 0; a < n; a++)
    for(b = 0; b < 2a; b++)
        for (c=0; c < b*b; c++)
            x++;

I simplified the running time for each line to be virtually (n+1) for the first loop, (2n+1) for the second loop, and (2n)²+1 for the third loop. Assuming the terms are multiplied together, and we extract the highest term to find the Big Oh, would the running time be n⁴, or would it still follow the usual running-time of n³?

I would appreciate any input. Thank you very much in advance.

Answer 1

You are correct, n*2n*4n² = O(n⁴).

The triple nested loop only means there will be three numbers to multiply to determine the final Big O - each multiplicand itself is dependent on how much "processing" each loop does though.

In your case the first loop does O(n) operations, the second one O(2n) = O(n) and the inner loop does O(n²) operations, so overall O(n*n*n²) = O(n⁴).