Re:The Median of a Trillion Numbers
by eru on Monday August 24, 2009 @09:00AM
(#782014)
And getting the exact number is already a linear problem.
[ Parent
| on HN ]
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.
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.