Sobre la complejidad de calcular la medida de ∪a i ,b i

Se muestra que la complejidad del árbol de decisiones para calcular la medida de la unión de n intervalos (posiblemente superpuestos) es Ω(n log n), incluso si se permiten comparaciones entre funciones lineales de los extremos de los intervalos. También se demuestra la existencia de un límite inferior Ω(n log n) para determinar si dos de n números reales están dentro de ∈ entre sí. Estos problemas ofrecen una excelente oportunidad para discutir los efectos del modelo computacional sobre la facilidad de análisis y sobre los resultados producidos.