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.
-
2$\begingroup$ If the only tool you have is comparison, how can you compute $M - A[i]$? $\endgroup$喜欢算法和数学– 喜欢算法和数学2021年10月10日 04:02:05 +00:00Commented Oct 10, 2021 at 4:02
-
1$\begingroup$ @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. $\endgroup$Emad– Emad2021年10月10日 05:41:33 +00:00Commented Oct 10, 2021 at 5:41
1 Answer 1
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.
-
$\begingroup$ Nice answer. $\quad\quad$ $\endgroup$喜欢算法和数学– 喜欢算法和数学2021年10月10日 17:59:36 +00:00Commented Oct 10, 2021 at 17:59