A Lower Bound on Supporting Predecessor Search in $k$ sorted Arrays

Carsten Grimm

We seek to perform efficient queries for the predecessor among $n$ values stored in $k$ sorted arrays. Evading the $\Omega (n\log k)$ lower bound from merging $k$ arrays, we support pre…