Los puntos clave no están disponibles para este artículo en este momento.
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/ 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.
Leslie G. Valiant (Mon,) studied this question.