Order of growth as worst case running time as a function of N

Question

Given the following code fragment:

int sum = 0;
for (int i = 1; i <= N; i++)
    for (int j = 1; j <= i*i; j++)
        for (int k = 1; k <= j*j; k++)
            sum++;

My assumption:

• Outer loop: O(N)
• Middle loop: O(N*N)
• Innermost loop: O(N*N)

Hence, total running time should be O(N^5), right?

Answer 1

A preliminary remark

sum(k=1,p,k^2) = p(p+1)(2p+1)/6 = O(p^3)
sum(k=1,p,k^6) = O(p^7)

Computation of complexity

1. The most inner loop runs from k=1 to j^2 so it does exactly j^2 operations.
2. The middle loop runs from j=1 to i^2 and at each step we do j^2 operations. According to my preliminary observation, by substituting p=i^2 in the first equation, we can compute the total operations as: i^2(i^2+1)(2*i^2+1)/6 for each value of i. This is an O((i^2)^3) = O(i^6) number of operations.
3. The outer loop runs from i=1 to n and does O(i^6) operations at each step. So we have O(n^7) operations.

References

• http://www.math.com/tables/expansion/power.htm