[racket] Looking for feedback on code style

On 9/9/10 1:27 PM, Will M. Farr wrote:
> Nevertheless, it sure feels like it's O(N) (I've experimented quite a
> bit with timing tests, and the simple argument about averages I gave
> before "feels right").

Your intuition is correct; it's a bit tricky, but not too tricky, to 
show that the algorithm runs in expected time O(N), and that can be 
strengthened to "with high probability". You can Google "randomized 
selection" to find PDFs or PPTs of lectures at major universities that 
show the calculations. (The ones I checked assume monotonicity -- that 
is, assuming that the recursion on the larger piece is more costly -- 
which really should be proved also.) I think we can end this part of the 
thread now, or at least take it to private e-mail, as what we're talking 
about no longer has a connection to Racket! --PR