4 ms·
> quicksort O(log(n)). Quicksort is O(n log n) average case and O(n^2) worst-case.
by hn9780470248775 11y ago
> quicksort O(log(n)).
Quicksort is O(n log n) average case and O(n^2) worst-case.
- jasode 11y agoYes, I saw that error after the edit window closed so I couldn't fix the typo. There has to be an extra "n" because qs has to touch every element at least once so a baseline complexity of O(n) is unavoidable. Hopefully, it didn't detract from the point that Knuth was talking about premature micro-optimizations and not design/architecture/algorithm optimization. Some inexperienced people are repeating "premature optimization" to try and win internet arguments instead of using it as nuanced advice to avoid wasting time.
- cossatot 11y ago>to try and win internet arguments is pretty much the antithesis of >to avoid wasting time.
- zeroonetwothree 11y agoIt depends on how you implement median selection. You can get O(n log n) worst case if you want.
- pjscott 11y agoTrue, though it's usually not worth the hassle. Most production implementations of quicksort just drop down to heapsort for the current sub-array if the stack gets too deep. https://en.wikipedia.org/wiki/Introsort https://en.wikipedia.org/wiki/Introsort