Q:

how to find one of the k smallest elements in n-k comparisions given that Array is unsorted and n is the size of the array

You are given two inputs: an integer k, and an array A containing n integers.
Give an algorithm to find 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 find a correct answer and why it satisfies the bound
on the running time. (Hint: there is a very easy way to solve this problem).

A:

For k=1 I can find the smallest element in n-1 comparisons - just go along the array and keep track of the smallest element seen so far.
For k=2 find the smallest element of the first n-1 elements in the array, using n-2 comparisons. This is the smallest element in the whole array unless the element you missed is smaller, in which case it is the second smallest, which is OK.
For general k, find the smallest element in the first n-k+1, neglecting the last k-1 elements in the array. The result is the smallest element unless up to k-1 of the remaining elements are smaller, in which case it is still among the k smallest elements, and you are OK.

