[racket] Looking for feedback on code style

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Thu Sep 9 10:04:05 EDT 2010

Noel Welsh wrote:

> I think this is great code -- very clear. For production use you have
> the wrong data structure (Lists are O(n) random access and length; you
> want O(1) vectors), but that doesn't matter for your use.

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)".

Posted on the users mailing list.