# 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 Commented Oct 16, 2021 at 9:53
• @mathworker21 You are right. We can assume that at most one variable is true. Commented 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). Commented 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. Commented Oct 17, 2021 at 10:13
• ... which is why I would prefer to cite instead of writing it up. Commented Oct 17, 2021 at 10:14