News for hackers. Stuff that matters.

A comment on Pattern-defeating quicksort. Parent comment

Re:Pattern-defeating quicksort by partycoder on Friday June 30, 2017 @02:52PM (#14672902)
Which decreases the space complexity but increases the time complexity.
[ Parent | on HN ]
Re:Pattern-defeating quicksort by _hrfd on Friday June 30, 2017 @04:04PM (#14673325)
No, the time complexity is the same: O(n log n). The author of the top answer links to his book, where you can find a proof of time complexity:

https://sites.google.com/site/algoxy/home/elementary-algorit...

[ Parent | on HN ]
Re:Pattern-defeating quicksort by EvgeniyZh on Friday June 30, 2017 @07:51PM (#14674323)
...but it increases run time. It's fine not to care on hidden constants while analyzing algorithms, but not while using them in real life
[ Parent | on HN ]