How to design a search algorithm with time complexity O(n log n)?

Question

Describe a O(n log n)-time algorithm that, given a set S of n integers and another integer x, determines whether or not there exist two elements in S whose sum is exactly x.

Im planning on using binary search for this.

ALGORITHM(S,x)
S=Insertion-Sort()
for i=1 to S.length
   n=x-S[i]
   if( Binary-Search(S,n) == true)
      return { S[i],n }


Binary-Search(A, v)
low=1
high=A.length

while low ≤ high
   mid=(low+high)/2

   if v = A[mid]
     return mid
   if v > A[mid]  
      low ← mid+1
   else
      high ← mid−1
 return NIL 

How do I find the time complexity of this algorithm? And if T(n) is not (n log n), what's the correct algorithm?

Answer 1

The overall order of an algorithm is dominated by the highest order of the individual pieces. You're starting out with an insertion sort whose worst-case performance is O(n^2) so you've already failed.

If you were to replace the sorting algorithm with a O(n log n) version then you'd have to look at what's left. You have a single loop of length n with a body that calls a binary search. A properly coded binary search is O(log n) so the result should be O(n log n). Adding two O(n log n) processes still leaves you with O(n log n).

There's an alternate faster way to do the second step but I'll leave that for you to discover. It wouldn't affect the overall result.

Answer 2

As the other answers point out, you can do it using an O(n log n) sort at first and then search for the complement of each element in O(log n) time each element, thus adding up to O(n log n) overall.

However, I think you can also do the following to have an O(n) algorithm.

Observe that if the sum of two numbers is x, one of them has to be >= x/2, and another <= x/2. So, divide the array into two parts by the pivot x/2, one that is greater and one which is less. This takes O(n) time. In case there are more than one element with value x/2, you are done.

Now build a hashtable of x-i for all elements i in the lower array. This takes O(n) time again.

Now search for each element in the high array in the hashtable in constant time per lookup. Thus, this too is O(n).

Hence, overall complexity, O(n).

Answer 3

For each element i:

• If x-i is in the hash table, we have our sum (i and x-i)
• Insert i into the hash table.

Total running time - O(n).