The input to the problem is an unsorted list of n distinct values, and an integer k, 1 <= k <= n.

The output of the problem is the kth smallest value in the list .

If k=1, then the output is the minimum value in the list. If k=n, then the output is the maximum value in the list. If k= n/2, then the output is the median value in the list.

One simple algorithm to solve the Selection problem is to simply sort the data, and then return the kth item in the sorted list. But this algorithm requires O(n log n) time to sort the list.

There is a far more complicated algorithm that uses divide-and-conquer to solve the Selection problem. The algorithm is too complicated to describe here, but the recurrence relation is the following:

T(n) = T( n/5 ) + T( (3n)/4 ) + n

T(k) = 1 for all k <= 20

In other words, the algorithm divides the problem into two subproblems, one of which is of size n/5 and the other subproblem is of size (3n)/4. This is a very unusual divide-and-conquer algorithm, because the sub-problems are NOT the same size.

For this exercise you must give a proof-by-induction that T(n) is O(n) by proving that:

T(n) <= 20 n, for all n >= 1