<p>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$.</p>

<p>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.</p>

CC BY-SA 3.0
2014-06-30T22:00:58.573Z
What makes you think it is possible to achieve what you want?  It will take $\Omega(n \sqrt{n})$ time (or $\Omega(n \sqrt{n}/\lg n)$ time) just to read all of the bits, and it seems obvious that there are problem instances where you need to read all of the bits. For instance, consider a problem instance where all of the numbers are zero, or where all the numbers are zero except one has a single bit set.  P.S. When you say "expected time", are you also averaging over all possible inputs?
D.W.
CC BY-SA 3.0
2014-07-01T09:19:13.313Z
That is true. I am not averaging overall inputs.
That is why I am asking for randomized solution rather than deterministic. I don't understand how this lower bound works in randomized setting.

Can you please elaborate why your argument also works in the randomized setting. Thnx.
sbzk
CC BY-SA 3.0
2014-07-01T14:05:01.820Z
@sbzk, I think Yao's lemma works here: Consider the set of instances with just one bit set to $1$, and suppose your input is uniformly drawn from these instances. The average performance of the best deterministic algorithm on this distribution bounds the performance of the best randomized algorithm on its worst-case instance from this input set. I think you could formally show that every deterministic algorithm needs to read $\Omega($all$)$ the bits on average.
usul
<lower-bounds><randomized-algorithms>
To find OR of $\sqrt{n}$ numbers each of $n$ bits?
sbzk
# To find OR of $\sqrt{n}$ numbers each of $n$ bits?

(Asked by: username_0 on 2014-06-30)

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.

**Tags:** lower-bounds, randomized-algorithms

> **Comments:**
> **username_1**: What makes you think it is possible to achieve what you want?  It will take $\Omega(n \sqrt{n})$ time (or $\Omega(n \sqrt{n}/\lg n)$ time) just to read all of the bits, and it seems obvious that there are problem instances where you need to read all of the bits. For instance, consider a problem instance where all of the numbers are zero, or where all the numbers are zero except one has a single bit set.  P.S. When you say "expected time", are you also averaging over all possible inputs?  
> **username_0**: That is true. I am not averaging overall inputs. That is why I am asking for randomized solution rather than deterministic. I don't understand how this lower bound works in randomized setting.  Can you please elaborate why your argument also works in the randomized setting. Thnx.  
> **username_2**: @username_0, I think Yao's lemma works here: Consider the set of instances with just one bit set to $1$, and suppose your input is uniformly drawn from these instances. The average performance of the best deterministic algorithm on this distribution bounds the performance of the best randomized algorithm on its worst-case instance from this input set. I think you could formally show that every deterministic algorithm needs to read $\Omega($all$)$ the bits on average.  

---

## 0 answers

