On 9/9/10 11:52 AM, Prabhakar Ragde wrote:
Selection can be done in O(n) time regardless of the value of k.
Ah, that's where I went wrong. I think I was confused by the Wikipedia text on introselect, where k is a constant (unrelated the kth smallest element).
The idea is to split the n elements into sets of 5, find the median of each set by an ad-hoc method, recursively find the median of the medians, and use that to partition the n elements as in the Quicksort method. That is guaranteed to remove about 3n/10 elements (every median smaller than the median of the medians, and two elements from each associated set). So you get a recurrence like T(n) = T(n/5) + T(7n/10) + O(n) which has a solution that is O(n). The constant is pretty high, though.
Thanks for the explanation. David _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
