We prove that any oblivious algorithm using space S to find the median of a list of n integers from {l,...,2n} requires time n(n log log_s n). This bound also applies to the problem of determining whether the median is odd or even. It is nearly optimal since Chan, following Munro and Raman, has shown that there is a (randomized) selection algorithm using only s registers, each of which can store an input value or O(log n)-bit counter, that makes only O(log log_s n) passes over the input. The bound also implies a size lower bound for read-once branching programs computing the low order bit of the median and implies the analog of P ≠ NP ∩ coNP for length o(n log log n) oblivious branching programs.
展开▼
