I should note that the code I posted also used randomness to select the pivot element, so the statements below apply to it, too. It's on average O(N) (where average can mean either "run many times on the same input" or "run on many inputs of length N").
Will On Sep 9, 2010, at 11:03 AM, Prabhakar Ragde wrote: > 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 > _________________________________________________ > For list-related administrative tasks: > http://lists.racket-lang.org/listinfo/users _________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
