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 predecessor queries in $O(\log n)$ time after $O(n \log( \frac{k}{ \log n} ))$ construction time. We establish that this is optimal for strict predecessor queries, i.e., every data structure supporting $O(\log n)$-time strict predecessor queries requires $\Omega(n \log( \frac{k}{ \log n} ))$ construction time.

In this short talk, we demonstrate how to establish a lower bound on the construction time of a data structure in the algebraic computation tree model using Ben-Or's technique. We highlight the general pattern of this approach and discuss its limitations. For the sake of self-containment, this talk also includes a short introduction to algebraic computation trees and Ben-Or's technique.