Basic Algorithm Analysis and Summation Notation

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 + 开发者_如何学JAVA2 (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.

---

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

---

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.

---

What you need to calculate is this:

S = sum(i in 1..n^2) sum(j in 1..i) sum(k in 1..6) 1

Now, the innermost sum is obviously 6, hence we have

S = sum(i in 1..n^2) sum(j in 1..i) 6
  = 6 sum(i in 1..n^2) sum(j in 1..i) 1

The innermost sum is just the sum of the first i numbers, which you should know is i(i + 1)/2, giving

S = 6 sum(i in 1..n^2) i(i + 1)/2
  = 3 sum(i in 1..n^2) i(i + 1)
  = 3 sum(i in 1..n^2) (i^2 + i)

We can separate this into two sums:

S = 3 [ (sum(i in 1..n^2) i^2) + (sum(i in 1..n^2) i) ]

The second sum there is just our old friend, the sum of the first n^2 numbers, so expanding that is easy.

The first sum there is a new friend, the sum of the first n^2 squares. You can google for that if you don't know it off hand.

Drop in the formulae, expand a little, tidy with a broom, and you should get your answer.

Cheers!