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