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

whilein do

ifx= A[i] then

returni

else

i←i+1

return−1

SophiaPretty

(5)

Status NEW Posted 05 Jan 2018 01:01 PM My Price 7.00

-----------  ----------- H-----------ell-----------o S-----------ir/-----------Mad-----------am ----------- Th-----------ank----------- yo-----------u f-----------or -----------you-----------r i-----------nte-----------res-----------t a-----------nd -----------buy-----------ing----------- my----------- po-----------ste-----------d s-----------olu-----------tio-----------n. -----------Ple-----------ase----------- pi-----------ng -----------me -----------on -----------cha-----------t I----------- am----------- on-----------lin-----------e o-----------r i-----------nbo-----------x m-----------e a----------- me-----------ssa-----------ge -----------I w-----------ill----------- be----------- qu-----------ick-----------ly

Not Rated(0)

• Buy Answer