[SOLVED] Loop invariant of a running sum array?

Loop invariant of a running sum array?

So I was given this algorithm :

Algorithm RunningSum(int[] A)
n = A.length;
for i = 2 to n do
A[i] = A[i] + A[i - 1]
end
return A;
end

and I need to find the loop invariant
but I can figure out what the output could be...
lets say I have a array

a[4]= {1,2,4,3}

will the output be a[4] = {1,3,6,7} from {1,(1+2),(2+4),(4+3)} or will it be a[4]={1,3,7,10} from {1,(1+2),(3+4),(7+3)}

Thanks in advance.

Solution

In computer science, a loop invariant is a property of a program loop that is true before (and after) each iteration.

For

"property of a program loop" .. that is true

We can also say "logical condition" or just boolean. ;)

For the given code/loop/algorithm:

Algorithm RunningSum(int[] A)
  n = A.length;
  for i = 2 to n do
    A[i] = A[i] + A[i - 1]
  end
  return A;
end

We can surely state, that:

i >= 2
AND i <= n (< or <= ..depends on your "language"...to be exact:)
AND accordingly (in the scope of i): A[i] == A[i] + A[i - 1] (equality! not assignment)
(n == A.length, A == A ... + all "tautologies" ;)

.. are all true "before (and after) each iteration", thus our "loop invariant(s)" (of concern)

Regarding "output"/algorithm interpretation, i more tend to:

a[4]={1,3,7,10} from {1,(1+2),(3+4),(7+3)}