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
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
