On the Optimality of Some Set Algorithms
Edward M. Reingold · Journal of the ACM · 1972
The establishment of lower bounds on the number of comparisons necessary to solve various combinatorial problems is considered.Some of the new results are : (a) given two finite sets of real numbers, A and B, where n = max ( I A I , I B I ), O(n.log n) comparisons are required to determine if A = B, even when comparisons are allowed between linear functions of the numbers; and (b) the maximum of a set of n real numbers cannot be computed in fewer than n -1 comparisons if comparisons of only linear functions of the numbers are permitted, but the maximum can be computed in Ilog2n] comparisons if comparisons are allowed between exponential functions of the numbers, KEY WORDS AND PHRASES: optimal algorithms, maximum of a set, determining set equality CR CATEGORIES: 5.24, 5.29