title: Can we do 4-sum algorithm in O(n^2)?
body: <p>this is related to the following question:</p>
  
  <p><a href="https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem">https://cs.stackexchange.com/questions/2973/generalised-3sum-k-sum-problem</a></p>
  
  <p>Without loss of generality, let's only consider even <code>k</code>, or just <code>k = 4</code>.</p>
  
  <p>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 <code>O(n^2)</code> time, but the sorting requires <code>O(n^2 log(n))</code> time.</p>
  
  <p>If we use a hashmap to store the sums as key and their corresponding index pairs as value, then all operations can run in <code>O(n^2)</code> time.</p>
  
  <p>Am I missing something in that post or is it true for even <code>k</code>, <code>k</code>-sum can run in <code>O(n^{k/2})</code> time?</p>
  
  <p>Thanks!</p>