On the complexity of computing the measure of ∪[a i ,b i ]
- 1 July 1978
- journal article
- Published by Association for Computing Machinery (ACM) in Communications of the ACM
- Vol. 21 (7) , 540-544
- https://doi.org/10.1145/359545.359553
Abstract
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.Keywords
This publication has 4 references indexed in Scilit:
- Impressions of Mathematical Education in the People's Republic of ChinaThe American Mathematical Monthly, 1977
- Can the Measure of be Computed in Less than O(n log n) Steps?The American Mathematical Monthly, 1977
- Finding nearest neighboursInformation Processing Letters, 1976
- On computing the length of longest increasing subsequencesDiscrete Mathematics, 1975