Worst-case performance of quickSort / getPivot

[Craig Dillabaugh]

On Sunday, 17 November 2013 at 02:43:05 UTC, Vladimir Panteleev
wrote:
> 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

Unless I misunderstand something I am pretty sure there is a
deterministic algorithm for finding the median in unsorted data:

http://www.cs.cmu.edu/afs/cs.cmu.edu/academic/class/15451-s07/www/lecture_notes/lect0125.pdf


>
>> 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?

Yeah, since you have to do O(n) work to partition the array,
whether you do O(1) work, or O(n) work to find your pivot really
doesn't matter. From a theoretical perspective anyway :o)