Howdy, Stranger!

It looks like you're new here. If you want to get involved, click one of these buttons!

Categories

Find ANY ONE of the k smallest elements

joey_stormjoey_storm Member Posts: 2
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!

Joey

Comments

Sign In or Register to comment.