0
$\begingroup$

There's lots of answers on the proof but I didn't find anything that regarded my difficulty directly.

Question ( From " Introduction to Algorithms ( Cormen ) " ):

enter image description here

Answer ( Found on the net ):

enter image description here

enter image description here

I don't understand the case where $ A[j] = v $ when we prove the maintenance step for before the j+1-th iteration ( after assuming $ A[j] \neq v $ for before j-th iteration ). why does the loop invariant hold in such case?

I don't exactly see how it makes sense since the program terminates in such case and so we're left out without having proved that $ A[j] \neq v $ for before the j+1-th iteration, but on the contrary we've shown that $ A[j] = v $ for before the j+1-th iteration, hence contradicting the assumption that $ A[j] \neq v $ for before j-th iteration.

$\endgroup$
2
  • 1
    $\begingroup$ When A[j]=v you don't proceed to the next iteration. In that case the program returns i, which is equal to j. When the program exists through line 5 there is nothing to prove. Line 5 is inside the IF and therefore, the condition in it must be satisfied. $\endgroup$
    – plop
    Feb 2, 2021 at 18:21
  • $\begingroup$ What the paragraph is trying to prove is the assertion that when the program exits through line 8 then we know that A[k]!=v for all k<A.length. For this you need to assume that always the condition A[j]=v will not be satisfied. $\endgroup$
    – plop
    Feb 2, 2021 at 18:27

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.