News for hackers. Stuff that matters.
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.
Re:The Median of a Trillion Numbers by eru on Tuesday August 25, 2009 @08:48AM (#784700)
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.

[1] http://en.wikipedia.org/wiki/Selection_algorithm