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.