Bill has an algorithm, find2D, to find an element x in an n x n array A. The alg
ID: 3638519 • Letter: B
Question
Bill has an algorithm, find2D, to find an element x in an n x n array A. The algorithm find2D iterates over the rows of A, and calls the algorithm arrayFind, of below code fragment, 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?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
while i < n do
if x = A[i] then
return i
else
i = i + 1
return -1
Explanation / Answer
The worst case run time of Find2D is O(n^2) and here is why: 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^2) An algorithm is said to have linear time if its worst case run time is O(n). Since it is O(n^2) for Find2D, it is not a linear time algorithm
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.