0
$\begingroup$

I am going through the fourth edition of Algorithms by Sedgewick & Wayne. On page 190 there is a discussion of lower bounds for the 2-sum problem, where the 2-sum problem is stated as: find all pairs of integers in an input array that sum to zero where each integer is distinct.

In the lower bounds discussion it says: Can we find algorithms for the 2-sum and 3-sum problems that are substantially faster than TwoSumFast and ThreeSumFast? Is there a linear algorithm for 2-sum or a linearithmic algorithm for 3-sum? The answer to this question is no for 2-sum (under a model that counts and allows only comparisons of linear or quadratic functions of the numbers).

The bolded section above doesn't make sense to me, as one could iterate through the elements in the array and store them in a set or a hash map. Then iterate through again and check if the negative of each element exists in O(1) time. This would effectively be O(n) or linear time.

The solution given in the text is to sort and then use binary search to check for the negative complement of each element in the array which is O(nlogn).

What am I missing here? I think it has something to do with this statement: under a model that counts and allows only comparisons of linear or quadratic functions of the numbers. But I'm not quite following what is meant by this statement or how using a hash map would violate this, considering binary search is a logarithmic function of the numbers.

$\endgroup$
1
  • 1
    $\begingroup$ Operations on hashtables are linear in the worst case, not $\mathcal{O}(1)$, which is the average complexity (not even amortized complexity). $\endgroup$
    – Nathaniel
    Mar 29 at 17:03

0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Browse other questions tagged or ask your own question.