I have the following simple algorithm to find the smallest element of an array $A$ of numbers:

m = A[0];
For i = 0 to A.length() do
    if m < A[i] then
        m = A[i];
return m;

The complexity of this algorithm is $O(n)$ where $n$ is the length of $A$.

I would like to prove the correctness of this algorithm using an invariant. Yet I don't know which invariant is nice here. Maybe something like: $m$ is the minimum of the subarray $A[1..k]$.

  • 2
    $\begingroup$ I think that invariant works perfectly for this algorithm. What are you stuck on exactly? $\endgroup$ – Nathan Feb 21 '19 at 14:03

The invariant is good (once you fix lots of imprecise things, like the 1..k which is obvious nonsense, and wouldn’t proof correctness. Precision is important. ) The code is broken, so your proof should fail - because it would be an invariant of a correct algorithm, but not your code posted here.


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.