Problem 4 [12 pts (3,3,3,3)]: Search Algorithms In binary search, we split the list in half, perform one comparison to determine if our target element is in the first or second half, and repeat on the appropriate half as necessary until only one element remains. Since there are at most log2 n halving operations, we use at most 1 log2n - log2n comparisons in the worst-case Now consider ternary search instead. Here we would split the list into thirds, perform (at most) 2 comparisons to determine which third contains our target element, and repeat on the appropriate third as necessary until only one element remains i. What is the worst-case number of comparisons performed by ternary search? Explain. ii. Which algorithm performs fewer comparisons in the worst-case, and by how much? Your answer should be in the form, "Algorithm A performs r-times fewer comparisons than Algo- rithm B" for appropriate values of A, B, and x. Hint: The following mathematical fact may come in handy; it allows one to change the base of a logarithm. loga nlog, n/log, a Let us now generalize to k-ary search, where we split the list into k equal size groups and perform (at most) k - 1 comparisons to determine the appropriate group on which to repeat. iii. What is the worst-case number of comparisons performed by k-ary search? Explain. iv. What is the integer value of k which minimizes the number of com parisons in the worst-case? Explain Hint: Ensure that your expression from parti is in the form f(k) log2n for some function f(k). To do this, make use of the fact that loga n-log, n/log, a, as you did above. Problem 4 [12 pts (3,3,3,3)]: Search Algorithms In binary search, we split the list in half, perform one comparison to determine if our target element is in the first or second half, and repeat on the appropriate half as necessary until only one element remains. Since there are at most log2 n halving operations, we use at most 1 log2n - log2n comparisons in the worst-case Now consider ternary search instead. Here we would split the list into thirds, perform (at most) 2 comparisons to determine which third contains our target element, and repeat on the appropriate third as necessary until only one element remains i. What is the worst-case number of comparisons performed by ternary search? Explain. ii. Which algorithm performs fewer comparisons in the worst-case, and by how much? Your answer should be in the form, "Algorithm A performs r-times fewer comparisons than Algo- rithm B" for appropriate values of A, B, and x. Hint: The following mathematical fact may come in handy; it allows one to change the base of a logarithm. loga nlog, n/log, a Let us now generalize to k-ary search, where we split the list into k equal size groups and perform (at most) k - 1 comparisons to determine the appropriate group on which to repeat. iii. What is the worst-case number of comparisons performed by k-ary search? Explain. iv. What is the integer value of k which minimizes the number of com parisons in the worst-case? Explain Hint: Ensure that your expression from parti is in the form f(k) log2n for some function f(k). To do this, make use of the fact that loga n-log, n/log, a, as you did above