contestada

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?

Respuesta :

akindelemf

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:

The worst-case running time of find2D in terms of n should be [tex]O(n^2)[/tex]

It is not the linear time algorithm.

Calculation of the worst-case:

Since the worst-case run time should be [tex]O(n^2)[/tex] Since the worst case run the time of array here we find is O(n) and this represent the function that should be called up for n rows from the find Find2D algorithm.

Also, An algorithm should be considered to have linear time in the case when it is worst case run time is O(n). Since it is [tex]O(n^2)[/tex] for Find2D, it is not a linear time algorithm

Learn more about linear here: https://brainly.com/question/22400798

Otras preguntas