Given $\sqrt{n}$ numbers of $n$ bits each. I need to find its OR and store it at another number RESULT of $n$ bits.Trivially it can be done in $\mathcal{O}(n \sqrt{n})$ time, or $\mathcal{O}(n \sqrt{n} \,/ \log n)$ considering RAM model with word size $\log n$.I am interested in some deterministic or randomized solution that takes $\mathcal{O}(n \text{ polyLog } n)$ time expected or exact to solve the problem. I need an exact solution but expected time will work.
To find OR of $\sqrt{n}$ numbers each of $n$ bits?
lower bounds;randomized algorithms