3. Recall that for integers a ...,an and an integer z, LinearSearch(r, a n) retu

Question

3. Recall that for integers a ...,an and an integer z, LinearSearch(r, a n) returns the index of z if r is one of the elements of the list a an or returns 0 if r is not part of the list. LinearSearch 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, and an integer z, BinarySearch(r, a 1, an) also returns the index of r if r is one of the elements of the list or returns 0 if r is not part of the list Binary Search has a runtime of e(log(m) in all cases. (a) Consider the following two search algorithms: procedure Searchl(a, a 1, an 1. return LinearSearch(r, a procedure Search2(a, a 1. si,..., sra Smart Sort an) 2. return BinarySearch 81, ...,Sn (*Assume that SmartSort has a runtime of e n log(n)) all cases.) i. Use e notation to describe the runtimes of Searchl 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 Searchl 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 r value, you wanted to search for n/2 values z1,... ,rn/2. Consider these two algorithms that each take as input a list of integers aj, an and another list of integers z n/2 and return an array Location, of length n/2 where Location is the index of r in the list a ...,an, and Location j is 0 if ri is not found in the list a

Explanation / Answer

3
a)

i)

Search1 is using LinearSearch whose best case time complexity is O(1) so time will be O(1)

Search2 is using a smallsort with best case time complexity of nlogn and then binary search which will take logn time. So best case will be O(nlogn)

ii) Worst case of Search1 will be worst case of linear search i.e., O(n)

Worst case of search 2 = worst case of small sort + worst case of binary search = O(nlogn) + O(logn) =O(nlogn)

b)

i)

SearchList1 : best run time for SearchList1 will be when array is sorted and search for first element but now as we have to search n/2 element

best time = 1 + 2 + 3 + 4+ ...+n/2 = O(n^2)

SearchList2: it will sort array in O(nlogn) time and then each search will take O(logn) time so total time

= O(nlogn) + nO(logn) = O(nlogn)

ii)

Worst case

Search1: Say all element are in extreme half so time will be = n + n - 1 + .... + n/2 = O(n^2)
Search2: Time will remian same as best case as both sort and search takes same time on all cases so O(nlogn)

Related Questions

Navigate

• Browse (All)
• Browse 3
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.