[racket] Looking for feedback on code style

 From: David Van Horn (dvanhorn at ccs.neu.edu) Date: Thu Sep 9 12:02:24 EDT 2010 Previous message: [racket] Looking for feedback on code style Next message: [racket] Literate Programming and Scribble Messages sorted by: [date] [thread] [subject] [author]

```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

```

 Posted on the users mailing list. Previous message: [racket] Looking for feedback on code style Next message: [racket] Literate Programming and Scribble Messages sorted by: [date] [thread] [subject] [author]