Random input helps searching predecessors

D. Belazzougui, A. C. Kaporis, P. G. Spirakis

We solve the dynamic Predecessor Problem with high probability (whp) in constant time, using only $n^{1+\delta }$ bits of memory, for any constant $\delta >0$. The input keys are random wrt a…