Prove that the loop invariant is true in the initialization stage, maintenance s

Question

Prove that the loop invariant is true in the initialization stage, maintenance stage, and prove that the loop invariant is true upon termination

Following is code for an algorithm for finding whether two numbers in a sorted array, A, sum to a given number, X. public static boolean twoNumbersEqua X(int[l A, int X) int start-0 int end A.length - 1; while (startend) int result = A[start] + A[end]; if (result ==X) return true; else if (result > X) end- else start++; return false; Consider the while loop. What is the loop invariant?

Explanation / Answer

The loop invariant is start must be strictly less than end.

Initialization stage:-

The loop invariant in initialization stage is TRUE as start is index of first element of sorted array and end is index of last element of sorted array. Since start < end in starting hence TRUE.

If array[start] + array[end] == x, we find our result and loop stops

Maintenance stage:-

if array[start] = array[end] > x implies end should be decremented because array elements are sorted in non-decreasing( or increasing) order.

if array[start] + array[end] < x implies start should be incremented to get higher value of array[start]

termination stage:-

while loop will terminate if we find the desired result == x within limitation of start < end returns TRUE,

otherwise no such pair for (start,end) exit with returning FALSE.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.