On the Complexity of Computing the Measure of U[ai, bi]

The decision tree complexity of computing the
measure of the union of n (possibly overlapping) 
intervals is shown to be  (n log n), even if comparisons
between linear functions of the interval endpoints 
are allowed.  The existence of an   (n log n) lower bound
to determine whether any two of n real numbers 
are within   of each other is also demonstrated.  These
problems provide an excellent opportunity for 
discussing the effects of the computational model on
the ease of analysis and on the results produced.

CACM July, 1978

Fredman, M.
Weide, B.

Analysis of algorithms, combinatorial problems,
computational complexity, computational models, 
decision tree programs, lower bounds

5.25 5.26 5.30 5.39

CA780702 DH February 8, 1979  3:46 PM

3086	5	3086
3086	5	3086
3086	5	3086