4 ms·
Thats a good point. Two things come t mind though. One is that since its an interview question they are probably just using this to test your knowledge of (di
by roundsquare 17y ago
Thats a good point. Two things come t mind though. One is that since its an interview question they are probably just using this to test your knowledge of (distributed) algorithms.
The second is that you might want the exact answer if you are using the statistic to convince someone of something and you don't want to leave any room for doubt.
- eru 17y agoAnd getting the exact number is already a linear problem.
- rjprins 17y agoIn 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