Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style

Reports tagged with Searching:
TR98-028 | 28th May 1998
Paul Beame, Faith Fich

On Searching Sorted Lists: A Near-Optimal Lower Bound

We obtain improved lower bounds for a class of static and dynamic
data structure problems that includes several problems of searching
sorted lists as special cases.

These lower bounds nearly match the upper bounds given by recent
striking improvements in searching algorithms given by Fredman and
Willard's ... more >>>

ISSN 1433-8092 | Imprint