Function CountEvenAn finds the number of occurrences of even

Function CountEven(A,n) finds the number of occurrences of even integers in n-element array A[1..n]:

CountEven(A,n)

1 cnt=0

2 for (i=1;i<=n;i++)

3 if (A[i]%2==0)

4 cnt++

5 return int

Prove correctness of CountEven using the loop invariant technique. Go through Initialization, Maintenance and Termination parts of the proof. The Loop Invariant is: “at the start of each iteration of the for loop, variable cnt contains the number of even elements in A[1...i-1]”

Solution

Initialization: Before the start of first iteration the invariant hold true as there are zero even numbers till then.

Maintainance: At the end of ith iteration the cnt contains some value which is total even numbers till that length. Now at the starting of i+1th iteration the count will have even numbers and if that number is not even then in i+2th iteration also cnt will show total even numbers till that length.

Termination: at the last iteration that is i=n+1 the cnt will have total number of evens present in the array of length n which is what this algorithm is supposed to do so it hold true there.