Re:The Median-of-Medians Algorithm
by virgi1 on Tuesday October 29, 2013 @09:10AM
(#6633770)
Yes you are. It's O(nlogn) where n is 5 - i.e. it's constant time (you can easily find the median by 4 comparisons to find the smallest of the 5, followed by 3 comparisons for the 2nd smallest, followed by 2 comparisons for the median - a total of 9 comparisons)
[ Parent
| on HN ]
Re:The Median-of-Medians Algorithm
by ihateloggingin on Tuesday October 29, 2013 @03:04PM
(#6636641)
Put otherwise: to sort them all it's O(n/5*(5 log 5)) = O(n).