Bounds on the time for parallel RAM's to compute simple functions
Stephen A Cook, Cynthia Dwork · 1982
We prove that a parallel RAM with no write conflicts allowed requires Ω(log n) steps to compute the Boolean or of n bits stored in the first n global memory cells. We first argue that this result is subtler than it appears, and in fact the “obvious” lower bound of log2n steps can be beaten.