Correctness of algorithm to find maximum in array

Question

I want to show correctness of "Algorithm to find maximum element in array" using induction and contradiction.

ans=-infinity
for (i=0; i<n; i++)
    ans= max(ans, A[i])

where A[0:n-1] is array and max is the function to return maximum of its two arguments.

What I am doing:

Base case: i=0, ans= max(-infinity,A[0])=A[0], as only one element has been processsed, it is maximum.

Induction Hypothesis: i=k<n-1, assume the algorithm correctly find maximum upto k iterations.

Inductive Step: i=k+1, let ans_{i} denote maximum element obtained by algorithm upto i steps and let ans'_{i} denote another maximum element from array A[0:i-1].

Then from induction hypothsis, ans_{k} = ans'_{k}

Now, for the sake of contradiction, assume ans_{k+1} < ans'_{k+1}

Now, how should I proceed to show this contradiction ?

Any suggestion? Should I change this approach ?

Answer 1

Tip: It's usually easy to proof by contradiction. Ignore the rest if you liked the suggestion.

Suppose you found some ans using your algorithm and ans is not the biggest.

If it's not the biggest, it means at some point, your ans was compared to a value X that's bigger than ans and max(ans, X) returned you ans.

Since max returns only the maximum value and X is bigger than ans, it's a contradiction.

---

By induction in the size n of the array, it's quite easy:

Base case: n = 1

• the algorithm will run and return the only element who is also the biggest [OK]

Hypohtesis: The algorithm works for any n

Inductive Step: It works for n+1

• Let's say you runned the first n elements of the array and you have your ans.

• Now you will just compare ans with the last element and you will return the biggest.

• As ans was the biggest from the first n elements (by hypothesis, we can find the biggest between n elements) and ans will be the maximum between ans and the last element, ans will be the maximum of the full array. [OK]

hope it helps.