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

this is related to the following question:

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!

• How would you sandwich with two pointers without sorting? – Navjot Singh Sep 12 '18 at 19:09
• Let s = $n^2$, then time needed to sort is $O(slogs)$ which is not equal to $O(n^2logn)$. – Navjot Singh Sep 12 '18 at 19:11
• Hashmap cannot store duplicates. So two pairs having same sum cannot be placed in the hashmap if sum is used as a key. Consider (1,3) and (2,2). – Navjot Singh Sep 12 '18 at 19:13
• @JotWaraich $O(n^2 \log(n^2))=O(n^2 2\log(n))=O(n^2 \log(n))$ – Kaa1el Sep 12 '18 at 20:11
• @JotWaraich in this case, either you don't need to store the duplicates (decision problem or return one such sum), or you can store in the value a list which consists of all such pairs (return all different sums). Either way, the complexity is not affected. – Kaa1el Sep 12 '18 at 20:13