News for hackers. Stuff that matters.

A comment on Big-O Algorithm Complexity Cheat Sheet. Parent comment

Re:Big-O Algorithm Complexity Cheat Sheet by gamegoblin on Saturday May 04, 2013 @06:11PM (#5656483)
You can use a randomized selection algorithm to find the median in linear time, and if you use the median as a pivot you will never get worst case n^2 behavior.

This is not used in practice because the probability of getting worst case behavior is extremely slim if you do some clever, and cheap, tricks.

[ Parent | on HN ]
Re:Big-O Algorithm Complexity Cheat Sheet by kolistivra on Sunday May 05, 2013 @01:04PM (#5659005)
Randomized selection algoritm is actually O(N^2) in the worst case. Median of medians is the O(N) worst case selection algorithm.
[ Parent | on HN ]