[racket] Looking for feedback on code style

From: Prabhakar Ragde (plragde at uwaterloo.ca)
Date: Thu Sep 9 12:03:43 EDT 2010

On 9/9/10 11:33 AM, Phil Bewig wrote:
> http://programmingpraxis.com/2009/12/11/selection/

This method takes O(n) time with high probability if the partitioning 
element is chosen deterministically and the data is randomly permuted 
(with all permutations equally likely) or if the partitioning element is 
chosen uniformly at random. Its deterministic worst-case cost is O(n^2). 
However, for a site called "Programming Praxis", it's definitely the 
right choice.

Our attitude towards randomness in computer science is a bit strange. 
I'm convinced most of our students graduate thinking that Quicksort is 
an O(n log n) algorithm, but this is only true in a probabilistic model. 
On the other hand, the shortest, cleanest, and most elegant method I 
know of to balance binary search trees (which underlies non-hash 
efficient set and map implementations) uses randomness, but no one talks 
about it or knows it. --PR

Posted on the users mailing list.