Question

Explain why the following algorithm is complete, correct, and finite.

Input: a list of n distinct integers a₀ to a_n-1 ordered from least to greatest and an integer x

Output: the index in the list at which x is found, or -1 if x is not found

Procedure:

i = 0

while (i <= n-1 and x != a_i)

   i = i + 1

if i < n then location = i

else location = -1

return location

Answer 1

To prove an algorithm correct, the program should have initialization, maintenance, and termination correct.
In this algorithm. This can be proved by the loop invariant technique.
Loop Invariant: At the start of the iteration, the variable 'i' does not hold any value. And at the end, every iteration 'i' will have some value.
Initialization: Initialization is done for the variable i.
Maintenance: Then, the value of x is matched with ai and as soon as x matches with ai, then the 'i' index is returned. Otherwise, if 'i' comes out to be zero only, it is assumed that the index is not available and hence, returned as -1.
Termination: The program terminates where the maximum index reaches n-1 or the value matches ai.

To prove the completeness of the algorithm, it should have a defined start, end and maintenance phase. Since, the program is starting at a point where i=0 and it keep on increasing until the value of 'i' reaches n-1 or value of x becomes ai. Hence, the program is complete.

To prove that the algorithm is finite, we need to define that the program will have a terminate condition. Here, the termination condition is already defined. So, the program will never run infinitely.

Friend, this was a really nice question to answer. If you find my answer helpful, please like it. Thanks.