<t>QuoteOriginally posted by: smiesQuicksort is O(n log n), but for median selection (or, for that matter, any element selection), once you've partitioned the data you only need to look at one half of it each time, so you average n + n/2 + n/4 + ... operations, which is O(n).Perhaps I'm misinterpret...