Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR17-050 | 15th March 2017 20:15

#### Non-Adaptive Data Structure Bounds for Dynamic Predecessor Search

TR17-050
Authors: Joe Boninger, Joshua Brody, Owen Kephart
Publication: 16th March 2017 06:27
A classic data structure of van Emde Boas [vEB75] solves dynamic predecessor search in $O(\log \log m)$ probes; this data structure is adaptive. For dynamic data structures which make nonadaptive updates, we show the cell probe complexity is $O\left(\min\{\frac{\log m}{\log(w/\log m)}, \frac{n\log m}{w}\}\right)$. We also give a nearly-matching $\Omega\left(\min\{\frac{\log m}{\log w}, \frac{n \log m}{w \log w}\}\right)$ lower bound. We also give an $\Omega(m)$ lower bound for memoryless data structures.