You are given two inputs: an integer k, and an array A containing n integers.
Give an algorithm to ?nd any one of the k smallest elements of A, using at most n - k comparisons. (In other words, your algorithm must return one of the k smallest elements of A, but it doesn't matter which one.) Explain why your algorithm is guaranteed to ?nd a correct answer and why it satis?es the bound on the running time. (Hint: there is a very easy way to solve this problem).
(b) Show that your algorithm from (a) is optimal by proving a lower bound of n - k on the number of comparisons required to solve the problem.