Lower bounds on non-adaptive data structures for median and predecessor search
Sivaramakrishnan Natarajan Ramamoorthy · Open Collections · 2017
We initiate the study of lower bounds for the median problem in the cell probe model. The algorithmic task is to maintain a subset of {1,2,....,m}, support insertion of elements and find the median of the set. Let $t_u,t_q,w$ denote the update time, the query time and the cell size of a data structure. We show that any data structure for the median problem must have $t_q \geq \Omega(m^(1/2(t_u+2))/(wt_u))$, when the updates are non-adaptive. An update is termed non-adaptive when locations of the cells accessed by the update algorithm is completely determined by the update value. For the predecessor search problem, we show that either $t_q \geq \Omega(\log m/(\log \log m + \log w))$ or $t_u \geq \Omega(m^(1/4(t_q+1)))$, when the queries are non-adaptive. This is joint work with Anup Rao.