# Proving an algorithm wrong

So I have this algorithm that outputs the largest value of an array:

• Input: $A[1,\dots,n]$, $n\geq 1$
• Output: Largest value of an array
Maximum (A)
m = A[1]
i = 1
while i < n
if A[i+1] > A[i]
m = A[i+1]
i = i+1
return m


I have to prove this algorithm wrong and I'm confused how to do that, because to me the algorithm seems correct. Any advice on how to do this are very much appreciated.

• Simple: give a counter-example, i.e. an input for which the algorith computes the wrong thing. – Raphael Apr 15 '18 at 19:29
• @Evander, be careful with indentation when you reformat code. – Peter Taylor Apr 16 '18 at 10:18

Consider the input $100,0,1$.

As a follow-up, identify the bug, and correct the algorithm.

• Hint: the code doesn’t do what it should do. Check the code literally as it is written, not as you think it should be written. It’s the kind of bug where you bang your head on the table and wonder how you could have ever missed it. – gnasher729 Apr 16 '18 at 14:34
• Don't forget that there are multiple solutions to a problem. As mentioned below you could rewrite the conditional, but an alternative is to strengthen the pre-condition to the code fragment: Insist the array is sorted, then the m will be assigned the maximum ;-) – Musa Al-hassy May 4 '18 at 13:10

Two points which will prove the algorithm is wrong

1. Array type starts with the zeroth element, in that case, A[0] will be eliminated even if it's the highest number. So, m should start with A[0], not A[1].
2. The comparison of each element should be made with the maximum number element(m) and not with its previous element. So, it should be A[i+1] > m, not A[i+1] > A[i]
• Your point 1 is besides the point. 0-based indexing is a choice. – Kai Apr 18 '18 at 6:40
• Why should the comparison be made with the current maximum rather than with the previous element? – Yuval Filmus Apr 18 '18 at 7:35