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