Recall that for integers a1, . . . , an and an integer x, LinearSearch(x, a1, .
ID: 3606032 • Letter: R
Question
Recall that for integers a1, . . . , an and an integer x, LinearSearch(x, a1, . . . , an) returns the index of x if x is one of the elements of the list a1, . . . , an or returns 0 if x is not part of the list. LinearSearch has a runtime of (1) in the best case, and (n) in the worst case.
Recall that for a sorted list of integers a1, . . . , an and an integer x, BinarySearch(x, a1, . . . , an) also returns the index of x if x is one of the elements of the list or returns 0 if x is not part of the list. BinarySearch has a runtime of (log(n)) in all cases.
(a) Consider the following two search algorithms: procedure Searchl(x,ai,... .an) 1. return LinearSearch(x,a., an) procedure Search2(z,a1,...,an) 1. SI, . . . , Sn-SmartSort"(ai, . . . , an) 2. return BinarySearch(x, s.,»n) (*Assume that SmartSort has a runtime of (n log(n)) in all cases.) i. Use notation to describe the runtimes of Search! and Search2 in the best case. which algorithm is more efficient in the best case? Justify your answers ii. Use notation to describe the runtimes of Search! and Search2 in the worst case, which algorithm is more efficient in the worst case? Justify your answers. (b) Suppose that n is even, and instead of searching for one z value, you wanted to search for n/2 values .. .*,/2- Consider these two algorithms that each take as input a list of integers ai,..., an and another list of integers ...m/2 and return an array Location, of length n/2 where Locations the index of r, in the list ai,...,an, and Locationj] is 0 if xj is not found in the list a1, ,an .Explanation / Answer
Solution:
a)
i)
The recurrence relation for Search1 is in best case is T(n)= c which means if the first element is the one which we are searching then it will take constant time to find the result so time complexity T(n) = O(1)
Search1 will perform better in best case because Search2 will be sorting the elements first which itself will take O(n log n) time.
ii)
In this case, as well Search1 will perform better because it will take O(n) time in the worst case and the Search2 algorithm will take O(n log n) time as given above.
b)
i)
In the best case, SearchList1 will take O(1) time at value of loop= 1, and O(2) time at value of loop= 2, and so on till the last value of loop= n/2, it will take O(n/2) time
Total time= 1+2+3+4+ ......+((n/2)-1) + (n/2)= (n/2) * ((n/2)+1)/2= O(n^2)
and SearchList2 will first sort the array in O(n log n) time than O(1) time everytime the loop iterates
so total time complexity= O(n log n) + O(n/2)= O(n log n)
we can see that in best case SearchList2 is performing better.
ii)
In the worst case SearchList1 will take total O(n^3) time whereas SearchList2 will take the same time as above O(n log n), so in worst case as well SearchList2 will perform better.
please rate and upvote..
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.