Research and Advances

On the complexity of computing the measure of ∪[ai,bi]

The decision tree complexity of computing the measure of the union of n (possibly overlapping) intervals is shown to be &OHgr;(n log n), even if comparisons between linear functions of the interval endpoints are allowed. The existence of an &OHgr;(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.

Advertisement

Author Archives

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved