Recall that for integers ai,... , an and an integer x, LinearSearch(x, ai,... , an) returns the index of r if z is one of the elements of the list a1,... , an or returns 0 if x is not part of the list. Assume that LinearSearch has a runtime of (1) in the best case, and 6(n) in the worst case. Recall that for a sorted list of integers a1, , an and an integer x, BinarySearch(z.al 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. Assume that BinarySearch has a runtime of (1) in the best case, and (log(n)) in the worst case. (a) Consider the following two search algorithms procedure Searchl(x, a1,... , an) 1. return LinearSearch(x, a1,... ,an procedure Search2(x, a1,... , an) 1. 81, An-SmartSort"(a1, , an) 2. return BinarySearch(x, s1,...,sn) (*Assume that SmartSort has a runtime of (n log(n)) in all cases.) . 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