Access Restriction

Author Weide, Bruce ♦ Fredman, Michael L.
Source ACM Digital Library
Content type Text
Publisher Association for Computing Machinery (ACM)
File Format PDF
Language English
Subject Keyword Decision tree programs ♦ Lower bounds ♦ Computational models ♦ Computational problems ♦ Combinatorial problems ♦ Analysis of algorithms ♦ Computational complexity
Abstract 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.
Description Affiliation: Carnegie-Mellon Univ., Pittsburgh, PA (Weide, Bruce) || The Univ. of California, San Diego (Fredman, Michael L.)
Age Range 18 to 22 years ♦ above 22 year
Educational Use Research
Education Level UG and PG
Learning Resource Type Article
Publisher Date 2005-08-01
Publisher Place New York
Journal Communications of the ACM (CACM)
Volume Number 21
Issue Number 7
Page Count 5
Starting Page 540
Ending Page 544

Open content in new tab

   Open content in new tab
Source: ACM Digital Library