Published on *Computer Science Department at Princeton University* (http://www.cs.princeton.edu)

We establish new lower bounds on the complexity of several searching problems. We show 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; m denotes the amount of storage used. This bound is provably tight for m = omega(n logc n) and any c > d - 1. We also prove a lower bound of

omega (n(log n/ log log n)d) on the time required for executing n inserts and queries. Other results include a lower bound on the complexity of orthogonal range searching in d dimensions (in report-mode). We show that on a pointer machine a query time of O(s + polylog(n)) time can only be achieved at the

expense of omega(n(log n/ log log n)d-1) space, which is optimal; n and s denote respectively the input and output sizes.

**Links**

[1] http://www.cs.princeton.edu/research/techreps/author/283

[2] ftp://ftp.cs.princeton.edu/techreports/1986/055.pdf