Finding Extrema With Unary Predicates
ID
TR-90-39
Publishing date
January 1990
Abstract
We consider the problem of determining the maximum and minimum elements ${x_{1}, \ldots ,x_{n}}$, drawn from some finite universe $\cal U$ of real numbers, using only unary predicates of the inputs. It is shown that $\Theta (n + \log |{\cal U} |) $ unary predicate evaluations are necessary and sufficient, in the worst case. Results are applied to i) the problem of determining approximate extrema of a set of real numbers, in the same model, and ii) the multiparty broadcast communication complexity of determining the extrema of an arbitrary set of numbers held by distinct processors.
File(s)