Can we do 4-sum algorithm in O(n^2)?

user_2858715 0
Viewed 1327

this is related to the following question:

https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem

Without loss of generality, let's only consider even k, or just k = 4.

My question is, after summing all pairs of numbers, is it necessary to sort the list of sums? I understand we could use two pointers from left and right to sandwich the two pairs in O(n^2) time, but the sorting requires O(n^2 log(n)) time.

If we use a hashmap to store the sums as key and their corresponding index pairs as value, then all operations can run in O(n^2) time.

Am I missing something in that post or is it true for even k, k-sum can run in O(n^{k/2}) time?

Thanks!

hash complexity-theory time-complexity algorithm
1 Answers

There are some subtleties, but you're right that average performance for the decision problem can be made that good. However it requires two hashmaps, not one.

The first hashmap is from the left, and it will store as value (i1, j1) where i1 < j1 and j1 is the minimum index for which that sum can be achieved.

The second hashmap is from the right, and it will store as value (i2, j2) where i2 < j2 and i2 is the maximum index for which that sum can be achieved.

Now run through the keys of the first hashmap, looking for the opposite in the other. If both are in there and j1 < i2 then you have your quadruple.

However note a subtlety. With sorting the expected and worst case time is O(n^2 log(n)). With a hash your expected time is O(n^2) but it is theoretically possible to get O(n^4) if your hashing algorithm breaks down. (Hashing algorithms don't generally break in practice, which is why we consider them O(1).)

user_5854110
Related