2
$\begingroup$

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.

$\endgroup$
2
  • 2
    $\begingroup$ If the only tool you have is comparison, how can you compute $M - A[i]$? $\endgroup$
    – John L.
    Oct 10 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
    Oct 10 at 5:41
2
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ Nice answer. $\quad\quad$ $\endgroup$
    – John L.
    Oct 10 at 17:59

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.