Sum of two integers in an array equals K

Question

I read Find two elements in an array that sum to k and How can I find two elements in an array that sum to k as they are related.

I know a O(n) solution but i see that a O(n logn) also exists :-

p=0,q=n-1;
while(p<q)
{
  if(a[p]+a[q]==k)
  {
      cout<<a[p]<<"\t"<<a[q];
      p++;
      q--;
   }
   else if(a[p]+a[q]>k)
      q--;
   else 
      p++;
}

This requires the array to be first sorted. But since the values of p and q are dependent on the elements in the array, how do we assert that the complexity of this algorithm is O(n Log n)?

According to me this algorithm is of O(n) complexity since at each iteration you are increasing or decreasing atleast one counter. — Abhishek Bansal, Oct 04 '13 at 07:09

score 1 · Accepted Answer · answered Oct 04 '13 at 07:31

The complexity of an efficient sorting algorithm is O(n log n).

No matter in what way the p and q changes, the while cycle will iterate through all the elements in the array once, thus it's complexity is O(n).

Adding the two together: O(n log n) + O(n) = O(n log n + n) = O(n log n), because n is much smaller than n log n, when n is a big number.

score 0 · Answer 2 · answered Oct 04 '13 at 07:10

If you have an O(n) solution, you don't need to concern yourself with an O(n log n) one since that's worse, unless the O(n) solution has some other problem like a massive space complexity like O(n^(n^(n^n))) :-)

In any case, the algorithm you have shown is also O(n) since you either increase the low index or decrease the high index on each iteration.

I suspect the O(n log n) you mention includes an initial sort of unsorted data first, since that's a typical time complexity for sorting.

Nikhil Rupanawar · Answer 3 · 2014-06-10T19:42:13.687

In python

arr = [1, 2, 4, 6, 10]
diff_hash = {}
expected_sum = 3
for i in arr:
    if diff_hash.has_key(i):
        print i, diff_hash[i]
    key = expected_sum - i
    diff_hash[key] = i

Algo:

Input: expected_sum

diff_hash = hashtable_datastructure
for(i=0, i<len(arr), i++)
{ 
   if(diff_hash(arr[i])) 
   { 
      return arr[i] , diff_hash(arr[i])
   } 
   key = expected_sum - arr[i] 
   diff_hash(key) = arr[i] 
 }

Sum of two integers in an array equals K

3 Answers3

Linked