To find an element x in an ordered array of size n, one might apply k-ary search: Split the array into k subarrays of roughly equal size, compare x to all border elements of these subarrays, and apply the algorithm recursively. a) Give the recurrence equation for the number of comparisons. b) Solve it exactly (!) for powers of k. c) What is the best choice of k? You have to prove your answer.