2
$\begingroup$

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 ?

$\endgroup$
  • $\begingroup$ You can tell it without contradictions: so from you induction step you have ans' as a maximum from 0 to $k-1$, then it is greater or equal all elements from 0 to $i-1$, when you look at the ans which is the maximum from 0 to $k$, it is max of two elements then greater or equal than these two elements then greater or equal of all elements up to index $k$ so induction step done and you proved for all $k$. $\endgroup$ – Eugene Dec 11 '16 at 10:32
  • $\begingroup$ can you show this contradiction ? $\endgroup$ – Sushil Verma Dec 11 '16 at 10:55
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.