Worst-case performance of quickSort / getPivot

[Vladimir Panteleev]

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?