News for hackers. Stuff that matters.

A comment on O(n^2), again, now in Windows Management Instrumentation. Parent comment

Re:O(n^2), again, now in Windows Management Instrumentation by hhmc on Monday December 09, 2019 @07:27PM (#21748329)
Quick sort can be made to be O(n log n) with careful choice of pivot - e.g. https://en.wikipedia.org/wiki/Median_of_medians
[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by kccqzy on Monday December 09, 2019 @07:49PM (#21748492)
Generally it is preferable to choose the pivot randomly.
[ Parent | on HN ]
Re:O(n^2), again, now in Windows Management Instrumentation by hhmc on Tuesday December 10, 2019 @07:51PM (#21758475)
Sure, and the wikipedia page makes mention of that. But it's not super relevant to the point I'm making about the worst-case complexity of quick sort (which is often misunderstood to be O(n^2)).
[ Parent | on HN ]