Re:The Median of a Trillion Numbers
by rjprins on Tuesday August 25, 2009 @04:00AM
(#784419)
In the ideal case you find the correct pivot immediately, but in worst case you will have to sort the whole list. Thus O(n) = n log n.
[ Parent
| on HN ]
No. You can find every order statistic in O(n) [1]. And even if someone handed you the pivot, you still had to prove that this is right.