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 Apr 27 '20 at 16:29

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, privacy policy and cookie policy

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