Question

Count the number of flops (floating point operations) in the following pseudocode:

for i=1:n  

for j=1:i    

for k=j:n      

y=y+aijxij    

end  

end

end

Answer 1

This question isn't really a matlab question. You can also apply brute force(checking every condition and add it) way of working it out.

Question.

for i=1:n  

for j=1:i    

for k=j:n      

y=y+aij * xij    

end  

end

end

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

2: Now Move to j loop (1 -> i ):

summation of 2(n-j+1) i times in j loop ( here q = 2(n-j+1) ) 

 it helps to know the sum of q from 1 -> i is i(i+1)/2 and q^2 from 1 to i is i(i+1)(2i+1)/6.

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

3: 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.



Total flipflop : f=n(n+1)(2n+1)/3.