LOWER BOUNDS ON THE COMPLEXITY OF MULTIDIMENSIONAL SEARCHING.

Research output: Chapter in Book/Report/Conference proceedingConference contribution

6 Scopus citations

Abstract

New lower bounds on the complexity of several searching problems are established. It is shown that the time for solving the partial sum problem on n points in d dimensions is at least proportional to (log n/log (2m/n))**d- **1 in both the worst and average cases, where m denotes the amount of storage used. This bound is probably tight for m equals OMEGA (n log**c n) and any c greater than d-1. A lower bound of OMEGA (n(log n/log log n)**d ) on the time required for executing n inserts and queries is also proved. Other results are presented.

Original languageEnglish (US)
Title of host publicationAnnual Symposium on Foundations of Computer Science (Proceedings)
Pages87-96
Number of pages10
DOIs
StatePublished - Dec 1 1986

All Science Journal Classification (ASJC) codes

  • Hardware and Architecture

Cite this

Chazelle, B. (1986). LOWER BOUNDS ON THE COMPLEXITY OF MULTIDIMENSIONAL SEARCHING. In Annual Symposium on Foundations of Computer Science (Proceedings) (pp. 87-96) https://doi.org/10.1109/SFCS.1986.29