# Best algorithm for solving $A[i] + B[j] = m$

Suppose $$A$$ and $$B$$ are arrays of real numbers of length $$n$$, and $$M$$ is another real number. One algorithm for finding indices $$i$$ and $$j$$ such that $$A[i] + B[j] = M$$ is to comparison-sort $$B$$ and run binary search with argument $$M - A[i]$$ on it $$n$$ times, which gives an $$O(n\log n)$$ algorithm. The source I have claims that this is "the best" algorithm for solving this problem. Why is this the best?

I think by best it means in terms of worst-case time complexity, i.e. its worst-case time complexity is better than any other algorithm, or equivalently, the worst-case time complexity of any algorithm solving this problem is $$\Omega(n\log n)$$.

Is this somehow related to theory of computation? The source is not famous that's why I won't mention its name. I guess we should also pay attention to the fact that the only tool we have is comparison so maybe the lower bound $$\Omega(n\log n)$$ for the worst-case of comparison-sort is somehow going to help us.

• If the only tool you have is comparison, how can you compute $M - A[i]$? Oct 10 at 4:02
• @JohnL. We have the other arithmetic and relational operations as well, or say any tool in writing a typical pseudocode(i.e loop, etc). What I meant was to emphasize comparison.
The kind of algorithm that you consider can be formalized in the algebraic decision tree model. In this model, there is an $$\Omega(n\log n)$$ lower bound on solving the set intersection problem, which is equivalent to your problem. See for example lecture notes of Jeff Erickson.
• Nice answer. $\quad\quad$ Oct 10 at 17:59