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)
