Title :
Information bounds are good for search problems on ordered data structures
Author :
Linial, Nathan ; Saks, Michael E.
Abstract :
The complexity of the search problem for a very broad class of data structures is estimated. The lower (Information Theoretic) bound and the upper bound differ by a small multiplicative constant.
Keywords :
Computer science; Data structures; Mathematics; Partitioning algorithms; Search problems; Upper bound;
Conference_Titel :
Foundations of Computer Science, 1983., 24th Annual Symposium on
Conference_Location :
Tucson, AZ, USA
Print_ISBN :
0-8186-0508-1
DOI :
10.1109/SFCS.1983.27
