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

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 hi开发者_如何转开发ghest 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.

---

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⁴).

---

Formally, using Sigma Notation, you can obtain this:

---

Could this be a question for Mathematics?

My gut feelings, like BrokenGlass is that it is O(n⁴).

EDIT: Sum of squares and Sum of cubes give a pretty good understanding of what is involved. The answer is a resounding O(n^4): sum(a=0 to n) of (sum(b=0 to 2a) of (b^2)). The inner sum is congruent to a^3. Therefore your outer sum is congruent to n^4.

Pity, I thought you might get away with some log instead of n^4. Never mind.