Input Array a Integer T left 1 right length of the array w

Input: Array a, Integer T. left = 1; right = length of the array; while (left

Solution

Here we are trying to get the sum of the elements of the loop if it is equal to a threshold the program returns true, and if left becomes greater than right the program returns false.

One of the variant will be to increase only the left by 1. We will achieve same thing by doing this and when left becomes equal to right the while loop terminates.

Induction:

suppose a=1,2,3,4,5

left=0, right=4. T=5.

on first iteration we get x=a[0]+a[4]=5, returns true.

on second we put T=6;

hence we do opns. x=[0]+a[4]=5, left++ ,x=[0]+a[4]=7, returns true.

Thus it can be said that this invariant holds true.