Question

Use the loop invariant (I) to show that the code below correctly computes the product of all elements in an array A of n integers for any n ≥ 1. First use induction to show that (I) is indeed a loop invariant, and then draw conclusions for the termination of the while loop.

Algorithm 1 computeProduct(int[ ] A, int n)
p = a[0]
i = 0
while i < n − 1 do
//(I) p = a[0] · a[1] · · · a[i] (Loop Invariant)
i + +
p = p · a[i]
end while
return p

Answer 1

Given Loop Variant P = a[0], a[1] ... a[i]

It is product of n terms in array

Step-by-step explanation:

The Basic Step: i = 0, loop invariant p=a[0], it is true because of 'p' initialized as a[0].

Induction Step: Assume that for i = n - 3, loop invariant p is product of a[0], a[1], a[2] .... a[n - 3].

So, after that multiply a[n - 2] with p, i.e P = a[0], a[1], a[2] .... a[n - 3].a[n - 2].

After execution of while loop, loop variant p becomes: P = a[0], a[1], a[2] .... a[n -3].a[n -2].

for the case i = n-2, invariant p is product of a[0], a[1], a[2] .... a[n-3].a[n-2]. It is the product of (n-1) terms. In while loop, incrementing the value of i, so i=n-1

And multiply a[n-1] with p, i.e P = a[0].a[1].a[2].... a[n-2].

a[n-1]. i.e. P=P.a[n-1]

By the assumption for i=n-3 loop invariant is true, therefore for i=n-2 also it is true.

By induction method proved that for all n > = 1 Code will return product of n array elements.

While loop check the condition i < n - 1. therefore the conditional statement is n - i > 1

If i = n , n - i = 0 , it will violate condition of while loop, so, the while loop will terminate at i = n at this time loop invariant P = a[0].a[1].a[2]....a[n-2].a[n-1]