Bill has an algorithm, find2D, to find an element x in an n×n array A. The algorithm find2D iterates over the rows of A, and calls the algorithm arrayFind, of Code Fragment 4.5, on each row, until x is found or it has searched all rows of A. What is the worst-case running time of find2D in terms of n? What is the worst-case running time of find2D in terms of N, where N is the total size of A? Would it be correct to say that Find2D is a linear-time algorithm? Why or why not?

Code Fragment 4.5: Algorithm arrayFind for finding a given element in an array.

The final justification technique we discuss in this section is the loop invariant. To prove some statement S about a loop is correct, define S in terms of a series of smaller statements S0,S1, . . . ,Sk, where:

1. The initial claim, S0, is true before the loop begins.

2. If Si−1 is true before iteration i, then Si is true after iteration i.

3. The final statement, Sk, implies the statement S that we wish to be true.

Let us give a simple example of using a loop-invariant argument to justify the correctness of an algorithm. In particular, let us consider using a loop invariant to justify the correctness of arrayFind, shown in Code Fragment 4.5, for finding an element x in an array A.

Algorithm arrayFind(x,A):

Input: An element x and an n-element array, A.

Output: The index i such that x = A[i] or −1 if no element of A is equal to x.

i←0

whilei<n do

ifx= A[i] then

returni

else

i←i+1

return−1