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.

Give the recurrence equation for the number of comparisons.

Solve it exactly (!) for powers of k.

What is the best choice of k?