CODEWITHSUNDEEP
algorithmloop-invariant
gongzhitaao
gongzhitaao

Reputation: 6682

What is the possible loop invariant

Could someone provide a possible loop invariant for the following simple algorithm:

Input: A[0,...,n-1] and B[0,...,m-1], each might contain repeated elements

Output: the first pair of (i,j) such that A[i] == B[j].

Algorithm:

for i <- 0 to n-1
    for j <- 0 to m-1
        if A[i] = B[j] then
           return (i,j)
        endif
    endfor
endfor
return null

So far, I've got only one solution that might or might not work:

S = {(i,j) | A[0,...,i-1] and B[0,...,j-1] has no common elements}

Upvotes: 0

Views: 122

Answers (1)

abeln
abeln

Reputation: 3759

At the beginning of the qth iteration of the second loop inside the pth iteration of the first loop, A[i] != B[j] for all i = 0...p - 1, j = 0...q - 1.

Upvotes: 2

Related Questions