On Sunday, 17 November 2013 at 01:48:14 UTC, Craig Dillabaugh
wrote:
1. Find the median value in the array. This can be done
deterministically in linear time,
My understanding that for unordered data, there is no algorithm
that runs in worst-case O(n):
http://en.wikipedia.org/wiki/Selection_algorithm
http://en.wikipedia.org/wiki/Quickselect
so from a theoretical point of
view is just as fast as picking a random element since you use
linear time.
Picking a random element is constant time, though. You mean that
O(1) and O(n) are equivalent here because they're both smaller
than O(n log n), QuickSort's complexity?
