Hacker News new | past | comments | ask | show | jobs | submit login

This article missed the last and most interesting bit: we know that Quicksort is O(nlogn) in the best case and O(n^2) in the worst case; what is it like on average? That is, what is the performance averaged over all possible inputs?

I can see why it was left out: the proof that Quicksort is O(nlogn) on average is much more complicated than anything in the article. (So, of course, my algorithms professor thought it would be a great homework problem. Cute.)

That said, the fact that it is O(nlogn) on average is actually well know--it's just the step from where the article left off to the conclusion that's missing. Wikipedia has an outline of the proof, if anybody is interested: http://en.wikipedia.org/wiki/Quicksort#Average_complexity




Applications are open for YC Winter 2022

Guidelines | FAQ | Lists | API | Security | Legal | Apply to YC | Contact

Search: