I think the other replies to you are mistaken. This algorithm meets the requirements of running in linear time, once you apply the inverting trick when the samp

I think the other replies to you are mistaken. This algorithm meets the requirements of running in linear time, once you apply the inverting trick when the sample size exceeds half of the pool size. See my top-level comment.