[net.lang] Time complexity of sort

mike@whuxl.UUCP (BALDWIN) (11/03/85)

For n numbers on one processor is O(n log n); for a sufficiently large
but finite number of processors in parallel is O(log n).  The algorithm
works by partitioning the numbers into sets ala divide and conquer, and
then the processors do a near-sort (i.e., the numbers are "almost" sorted)
and a merge until you get to the top of the tree.
-- 
						Michael Baldwin
						{at&t}!whuxl!mike

ark@alice.UucP (Andrew Koenig) (11/03/85)

If I remember right, even though the time complexity of sort is O(log n)
on a single processor, the median of a set can be found in O(n).
It is hard to imagine how this might be done, but...

barmar@mit-eddie.UUCP (Barry Margolin) (11/07/85)

In article <4516@alice.UUCP> ark@alice.UucP (Andrew Koenig) writes:
>If I remember right, even though the time complexity of sort is O(log n)
>on a single processor,

You remember wrong, it is O(n log n) on a uniprocessor.  With enough
processors (either n or log n, I'm not sure) it becomes O(log n).

>the median of a set can be found in O(n).
>It is hard to imagine how this might be done, but...

You don't have to imagine, you can read the Programming Pearls column of
the latest CACM, in which this very problem is discussed.
-- 
    Barry Margolin
    ARPA: barmar@MIT-Multics
    UUCP: ..!genrad!mit-eddie!barmar