TY - GEN

T1 - LOWER BOUNDS ON THE COMPLEXITY OF MULTIDIMENSIONAL SEARCHING.

AU - Chazelle, Bernard

PY - 1986

Y1 - 1986

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=0022877548&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0022877548&partnerID=8YFLogxK

U2 - 10.1109/SFCS.1986.29

DO - 10.1109/SFCS.1986.29

M3 - Conference contribution

AN - SCOPUS:0022877548

SN - 0818607408

SN - 9780818607400

T3 - Annual Symposium on Foundations of Computer Science (Proceedings)

SP - 87

EP - 96

BT - Annual Symposium on Foundations of Computer Science (Proceedings)

ER -