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 Algorithm 1.12, on each one, 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? Is this a linear-time algorithm? Why or why not?

Question

Jazmin

Mathematics

24 March, 06:28

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 Algorithm 1.12, on each one, 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? Is this a linear-time algorithm? Why or why not?

+2

Answers (1)

Know the Answer?

Terrance Mcconnell · Answer 1

The worst case run time of Find2D is O (n²) because the worst case run time of arrayFind is O (n) and this function will be called for n rows from Find2D algorithm, hence O (n²).

An algorithm is said to have linear time if its worst case run time is O (n). Since it is O (n²) for Find2D, it is not a linear time algorithm