Computing the maximum and the median
- 1 October 1971
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
This note is concerned with the number of binary comparisons required to compute the maximum or the median of sets of numbers. The new results are: (a) the maximum of a set of n integers cannot be computed in fewer than n-1 comparisons if comparisons of only linear functions of the integers are permitted, but the maximum can be computed in log2 n comparisons if comparisons can be made between exponential functions of the integers and (b) the median of a set of n integers can be computed using only 2n comparisons if comparisons between polynomial functions of the integers are permitted.Keywords
This publication has 0 references indexed in Scilit: