Basic Algorithm Analysis and Summation Notation

Question

So for a homework we had to count the number of steps in a piece of code. Here it is:

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

My prof (i think) explained that the number of operations in the 2nd line could be found using summation notation, like so:

n^2
Σ   x 4 + 3 
i=1

which would be 1/2(n^4 + n^2) x 4 + 3 = 2n^4 + 2n^2 + 3

but from just looking the line, I would think it would be something like 4n^4 + 2 (my prof said 4n^4 + 3, I'm not sure where the third operation is though...)

Am I doing the summation notation wrong here? It made sense to me to do summation notation for nested for loops, but I don't know why it would work for a for loop by itself.

Thanks.

Answer 1

Actually even your prof result is wrong. The exact result is 3n^4+3n^2.

To obtain that result simply consider:

All passages are pretty simple (the passage from step 4 to step 5 is immediate if you consider the formula for the sum of the firsts n natural numbers).

Answer 2

I guess both you and your professor are wrong. According to my calculation (I might be wrong too) it should be 3n^4+3n^2.

The outer most loop will run n^2 times. Taken this into consideration the inner loop will run 1 time for the first iteration and so on till n^2. i.e. from j=1 to j=1,2,3,4 ... n^2. If we sum the series (1+2+3...n^2) this becomes (n^2(n^2+1))/2.

So for n^2 iterations of outer loop the inner loop will execute (n^2(n^2+1))/2 times. The most inner loop executes six times for every iteration of the second loop. So by just multiplying (n^2(n^2+1))/2 with 6 it evaluates to 3n^4+3n^2.

To check the answer let's take an example. Say n=5, run your algorithm and print the sum this will give 1950. Now substitute this value in the evaluated expression, this will be like 3(5^4)+3(5^2) and again this evaluates to 1950.