Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
I have to solve this exercise:
Given an unordered array $A[1], \ldots, A[n]$ of positive and negative integers, determine if there are two indices $i \neq j$ such that $A[i] + A[j] = 0$. Establish a lower limit to the problem using the decision tree technique.
The solution should be $Ω(\log s(n))$, where $s(n)$ is number of possible solutions, in this case $n^2$.
But, I don't understand why the number of possible solutions is $n^2$ rather than $\binom{n}{2}$.
You're right that there are only $\binom{n}{2}$ many inequivalent solutions. Fortunately, $\Omega(\log \binom{n}{2}) = \Omega(\log n)$, so there isn't much difference between $\binom{n}{2}$ and $n^2$, in this regard.
However, this is a pretty bad lower bound. You haven't specified which queries are allowed, but assuming you're allowed to compute signs of constant degree polynomials, then I would expect an $\Omega(n\log n)$ lower bound, since the similar problem Element Distinctness has such a lower bound. This also matches the upper bound obtained by sorting (assuming your model supports this).
Indeed, this is just 2SUM (a sibling of the more famous 3SUM problem), and an $\Omega(n\log n)$ lower bound was proved by Chan, Gasarch and Kruskal in their paper Refined Upper and Lower Bounds for 2-SUM.
