Binary Search prunes 1/2 of the search space on each recursive iteration. Ternary Search prunes 2/3 of the search space on each recursive iteration. Does it make ternary search better than binary search? This problem will help you to find out. The following is the algorithm for Ternary Search using the conventions from the Binary Search algorithm shown during lectures:

(a) Determine the runtime expression for Ternary Search in terms of the input size. Use constants 3 for the base case, and 4 for the recursive case. (b) Consider the runtime expressions for Binary Search discussed during lectures. Let 1 and 3 be the maximum number of compares to execute for the base cases in Binary Search and Ternary Search, respectively. Similarly, let 2 and 4 be the maximum number of compares to execute for the recursive steps, respectively. Does Ternary Search perform better than Binary Search in terms of the input size? State your reasoning.

Algorithm TernarySearch(A, X, 1, r) if (r X) return TernarySearch(A, X, 1, m1 - 1) else if (A[m2]