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

Mathematics

Rachael Norton

31 July, 16:04

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?

+4

Answers (1)

Know the Answer?

Tessa Wolfe · 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