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}$.

  • $\begingroup$ Asymptotically speaking $n^2$ and $\binom{n}{2}$ are the same. Maybe whoever gave you the solution implicitly used one for the other (this won't affect the lower bound since you're using the big omega notation anyways). $\endgroup$
    – Steven
    Commented Apr 27, 2020 at 16:29

1 Answer 1


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.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.