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.