# [racket] Looking for feedback on code style

 From: David Van Horn (dvanhorn at ccs.neu.edu) Date: Thu Sep 9 11:26:17 EDT 2010 Previous message: [racket] Looking for feedback on code style Next message: [racket] Looking for feedback on code style Messages sorted by: [date] [thread] [subject] [author]

```On 9/9/10 10:04 AM, Prabhakar Ragde wrote:
> I don't think vectors help very much in this case (median-finding). For
> the given code, the O(n) access to the middle of the list is dominated
> by the cost of the sorting, which is at least O(n log n) [*].
>
> It is theoretically possible to compute the median in O(n) time, but the
> method is complicated and not very practical. But sorting definitely
> does too much work. If only the median (or the kth largest, a problem
> called "selection") is needed, a method which is both practical and of
> pedagogical interest stems from adapting Quicksort, which is a good
> exercise after section 25.2 of HtDP. This has expected cost O(n) on
> random data, and vectors offer no asymptotic advantage over lists. --PR
>
> [*] Technically, "at least Omega(n log n)".

The original post got me interested in median algorithms and I started
to read up on the selection problem.  Wikipedia (I know, I know) says
the same thing as you: medians can be computed in O(n) time and points
to selection as the way to do it.  But I don't see how to use selection
to achieve a O(n)-time median algorithm -- selection (of the kth
largest/smallest element) is O(n), but that's were k is some fixed
constant.  To compute the median, you let k=n/2 (right?), so it's no
longer constant.  Can you point me to (or sketch) a O(n) method?  Or
just correct me if my reasoning is going astray.

Thanks!

David

```

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