Asymptotic analysis of three interdependent nested for loops

Question

The code fragment I am to analyse is below:

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

I know that the first loop is O(n) but that's about as far as I've gotten. I think that the second loop may be O(n^2) but the more I think about it the less sense it makes. Any guidance would be much appreciated.

Answer 1

The first loop executes n times. Each time, the value i grows. For each such i, the second loop executes i*i times. That means the second loop executes 1*1 + 2*2 + 3*3 + ... + n*n times.

This is a summation of squares, and the formula for this is well-known. Hence we have the second loop executing (n(1 + n)(1 + 2 n))/6 times.

Thus, we know that in total there will be (n(1 + n)(1 + 2 n))/6 values of j, and that for each of these the third loop will execute 1 + 2 + ... + j = j(j+1)/2 times. Actually calculating how many times the third loop executes in total would be very difficult. Luckily, all you really need is a least upper bound for the order of the function.

You know that for each of the (n(1 + n)(1 + 2 n))/6 values of j, the third loop will execute less than n(n+1)/2 times. Therefore you can say that the operation sum++ will execute less than [(n(1 + n)(1 + 2 n))/6] * [n(n+1)/2] times. After some quick mental math, that amounts to a polynomial of maximal degree 5, therefore your program is O(n^5).

Answer 2

int sum = 0;                  
for (int i = 0; i < n; i++)            // Let's call this N
   for (int j = 0; j < i * i; j++)     // Let's call this M
      for (int k = 0; k < j; k++)      // Let's call this K
         sum++;

N is the number of steps of the entire program, M is the number of steps the two inner loops do and lastly K is the number of steps the last loop does.

It is easy to see that K = j, it takes j steps to do.

Then M = Sum(j=0,i^2,K) = Sum(j=0, i^2, j)

(First param is the iterator, second is the upper bound and last param is what we are adding)

This is actually now a sum of n numbers to i*i. Which means we can apply the formula ((n+1)*n)/2

 M = Sum(j=0,i^2,j) = ((i^2+1)*(i^2))/2 = (i^4 + i^2)/2

 N = Sum(i=0, n, M) = 1/2 * ( Sum(i=0, n, (i^4)) + Sum(i=0, n, (i^2)) )

These are both well known formulas and after a little playing you get:

 N = (n^5)/10 + (n^4)/4 + (n^3)/3 + (n^2)/4 + n/15

This should be the exact number of steps the loop takes, but if you are interested in the O notation you can note that n^5 is the strongest growing part so the solution is O(n^5)