Loop invariant of a running sum array?

Question

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.

the algorithm is a description of [Fibonacci Series](https://www.programiz.com/java-programming/examples/fibonacci-series). Here is a related post about [Fibonacci Loop Invariants](https://math.stackexchange.com/questions/1444398/fibonacci-loop-invariants) — Sharon Ben Asher, Apr 30 '23 at 14:16

MaBed · Answer 1 · 2023-04-30T14:39:14.410

0

This may vary in some programming languages, but most common languages will produce the output {1,3,7,10}. The best way to find out is just run the code and print the output.

edited Apr 30 '23 at 14:39

answered Apr 30 '23 at 14:11

MaBed

178
8

xerx593 · Accepted Answer · 2023-04-30T19:17:21.567

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

Source: https://en.m.wikipedia.org/wiki/Loop_invariant

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

.#

score 0 · Answer 3 · answered Apr 30 '23 at 19:23

0

This is a scan or prefix-sum operation. The invariant at the start of the loop body is that

in iteration i, A[i] is the sum of all previous A[j]

plus stuff about bounds and such.

answered Apr 30 '23 at 19:23

Victor Eijkhout

5,088
2
22
23

Loop invariant of a running sum array?

3 Answers3