On Thu, Sep 9, 2010 at 5:03 PM, Prabhakar Ragde <plra...@uwaterloo.ca> wrote: > 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.
"What is the average and worst case complexity of Quicksort?" is a first round interview question at Google (that is, the "HR person reading questions off a list" stage). A friend was asked this a few weeks ago. This is a great thread. N. _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
