Hey guys, I was hoping someone could help me out with this problem, I might be over thinking it too much and the answer might be very simple but its not getting to me.
The problem has to deal with the k-smallest element problem, you are given n elements and an integer k such that 1 < k < n. The problem is to find ANY ONE of the k smallest elements.
So for example, if k = 4, the output may be either the first, second, third, or fourth-smallest element.
I am looking for a FAST algorithm to solve this problem and to figure out how many comparisons it performs. I also need to give a lower bound as a function of n and k on the number of comparisons needed to solve this problem.
Any help is appreciated, thanks!