Counting the number of flops

Question

For the following pseudocode; I think that the number of flops is 2n^3. However, I am unsure that this is correct as the for loops make me doubt it. (Note: aij and xij represent entries for matrices A and X respectively)

for 𝑖=1:𝑛
  for 𝑗=1:𝑖
    for 𝑘=𝑗:𝑛
      𝑦=𝑦+𝑎𝑖𝑗*𝑥𝑖𝑗    
    end
  end
end

Answer 1

This isn't really a matlab question. Here is a brute force way of working it out.

The inner equation has two flops, so the k loop has 2(n-j+1) flops.

To do the rest, it helps to know the sum of q from 1 to p is p(p+1)/2 and q^2 from 1 to p is p(p+1)(2p+1)/6.

The j loop is of 2(n-j+1) for j from 1 to i, so it has 2i(n+1)-i(i+1)=2i(n+1/2)-i^2 flops.

The overall, or i, loop is a sum of 2i(n+1/2)-i^2, giving n(n+1)(n+1/2) - n(n+1)(2n+1)/6 = n(n+1)(2n+1)/3.

You can see that this is the same as the sum from 1 to n of 2i^2.

A way to check this, e.g. in matlab, is to set some n, and put f=0 at the start and replace the inner equation with f=f+2;, then the result will be f=n(n+1)(2n+1)/3.