Recall that for integers ai and an integer r, LinearSearch(r, a1 an) returns the
ID: 3820692 • Letter: R
Question
Recall that for integers ai and an integer r, LinearSearch(r, a1 an) returns the index of z if r is one of the elements of the list a an or returns 0 if z is not part of the list. Search has a runtime of e(1) in the best case, and e(n) in the worst case. Recall that for a sorted list of integers a1 an and an integer z, BinarySearch(r, an) also returns the index of z if z is one of the elements of the list or returns 0 if z is not part of the list. Binary Search has a runtime of e(log(n)) in all cases.Explanation / Answer
i) SeacrhList1
Best case will be when seach item are in order from begining
so time taken will be 1 + 2 + 3 + 4 + 5 + 6 + 7 +....n/2 = O(n^2)
SearchList2
smartsort will take O(nlogn)
and each n/2 search operation will take O(logn) = Onlogn)
Total time - O(nlogn)So searchList2 perform better than search list 1 in best case.
ii) SeacrhList1
Worst case will be when seach item are in order from last
so time taken will be n + n-1+n-2....+n/2+1 = O(n^2)
SearchList2
smartsort will take O(nlogn)
and each n/2 search operation will take O(logn) = O(nlogn)
Total time - O(nlogn)
So searchList2 perform better than search list 1 in worst case.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.