The inherent complexity of dynamic data structures which accommodate range queries
- 1 October 1980
- proceedings article
- Published by Institute of Electrical and Electronics Engineers (IEEE)
Abstract
A formal framework is presented in which to explore the complexity issues of data structures which accommodate various types of range queries. Within this framework, a systematic and reasonably tractable method for assessing inherent complexity is developed. Included among the interesting results are the following: the fact that non-linear lower bounds are readily accessible, and the existence of a complexity gap between linear time and n log n time.Keywords
This publication has 4 references indexed in Scilit:
- A Lower Bound on the Complexity of Orthogonal Range QueriesJournal of the ACM, 1981
- Lower Bounds on the Complexity of Some Optimal Data StructuresSIAM Journal on Computing, 1981
- A data structure for orthogonal range queriesPublished by Institute of Electrical and Electronics Engineers (IEEE) ,1978
- How good is the information theory bound in sorting?Theoretical Computer Science, 1976