The worst-case time complexity of algorithms for multiprocessor computers with binary comparisons as the basic operations is investigated. It is shown that for the problems of finding the maximum, sorting, and merging a pair of sorted lists, if n, the size of the input set, is not less than k, the number of processors, speedups of at least O(k/log log k) can be achieved with respect to comparison operations. The algorithm for finding the maximum is shown to be optimal for all values of k and n.
No takes yet. Share an insight, caveat, or question.
Leslie G. Valiant (1975) studied this question.
Synapse has enriched one closely related paper. Consider it for comparative context: