(b) Suppose that n is even, and instead of searching for one x value, you wanted to search for n/2 values ri,... ,^n/2. Consider these two algorithms that each take as input a list of integers a1,..., an and another list of integers x1,..., ln/2 and return an array Location, of length n/2, where Location il is the index of x in the list a in the list a1,... , an- l, , an, and L ocationil is 0 if xi is not found procedure SearchListl(ai,... , an,xi,... ,xn/2) 1. for i -1,... ,n/2 2. Location[i] = LinearSearch(zi,ai, ,an) 3. return Location procedure Searchlist2(a1,- ..,an,Ti, -.. , Tn/2 1. s?, , sn-SmartSort"(al' 2, for i = 1, . n/2 , an) Location [i] = BinarySearch (zi , 81 , . . . , sn ) 4. return Location (*Assume that SmartSort has a runtime of ?(n log(n)) in all cases.) i. (4 points) 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. (4 points) 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