# Lower bound for the OR problem

Let us have booleans $$x_1, \cdots, x_n$$. Any algorithm that determines $$\bigvee_1^n x_i$$ with probability at least $$2/3$$ requires $$\Omega(n)$$ time. It is not too difficult to prove this, but the proof would certainly be more than a few lines. I have seen a paper that proves this, but cannot find it. Does anyone know of such a paper? I need this in my paper (I am doing a reduction from this problem) and would prefer not to repeat the argument if someone has written it up in detail already. Any result which would imply this in a few lines would be useful, too.

• what if some $x_j$ is true and all the others are false? doesn't that show an $\Omega(n)$ lower bound? i could be wrong Oct 16, 2021 at 9:53
• @mathworker21 You are right. We can assume that at most one variable is true. Oct 16, 2021 at 16:16
• @domotorp Thanks. Yes, I should have said "at most one" instead (otherwise, just always outputting 'true' satisfies the family I gave). Oct 16, 2021 at 20:46
• That is not a formal proof. While what you are suggesting works directly for deterministic algorithms, the lower bound for randomized algorithms is slightly more technical. Oct 17, 2021 at 10:13
• ... which is why I would prefer to cite instead of writing it up. Oct 17, 2021 at 10:14

## 1 Answer

After some more searching, I managed to find a proof in these lecture notes [1]. The proof goes via Yao's principle and the lower bound is n/3. If someone knows of a published paper or a book that I may cite for this fact, I am still interested.