Question

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?

Answer 1

Answer:

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

Step-by-step explanation: