4 ms·
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.
by rjprins 17y ago
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.
- eru 17y agoNo. 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 http://en.wikipedia.org/wiki/Selection_algorithm