Big theta please explain

3. Recall that for integers a1, an and an integer z, Lin a,a1,... an) returns the index of z earSearch if z is one of the elements of the list a1,... an or returns 0 if ze 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, an and an integer z, B (z,a1, 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. Binarysearch has a runtime of e(log(n)) in all cases (a) Consider the following two search algorithms: procedure Searchl an) 1. return LinearSearch(r,a1, procedure Searc a1,...,an) 1. 81,..., sn martSort a1 an) 2. return BinarySearch(a, s1,...,sn) Assume that SmartSort has a runtime of e(nlog(n)) in 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 e notation to describe the runtimes of Searchl and Search 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 n/2 Consider these two algorithms that each take as input a list of integers a1, ...,an and another list of integers zi, and return an array Location, of length n/2, where Locationli] is the index of zi in the list a1 an, and Locationli) is 0 if zj is not found in the list a1,...,an