(a) (8 pts) Assume that the given list has been sorted in ascending order. Give a recursive Divide-and-Conquer final search algorithm (in pseudocode) which first tests the element at position n/4 for equality with some value x, and then possibly checks the element at position 3n/4. The result is either discovering x or reducing the set size to a fraction of the original. (b) (6 pts) Give the recurrence relations of final search algorithm. (c) (9 pts) Give the best-case, worst-case and average-case complexity of final search algorithm? No Justifications needed. Best-case Complexity Worst-case Complexity Average-case Complexity