Describe a $\Theta(n \lg 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$.

If the running time constraint was not there, we might have intuitively used the brute-force method of picking one element at a time and iterating over the set to check if there exists another element in the set such that sum of them is $x$. Even in average case, this brute-force algorithm will run at $\Theta(n^2)$ time (as we have to iterate over the set for each element).

But we have to think of a $\Theta(n \lg n)$-time algorithm.

TIP: Every time we see $\lg n$, we should think of divide-and-conquer algorithms.

So, the problem asks for a search algorithm and binary search is an efficient one at that which runs at $\Theta(\lg n)$ time for a sorted array.

So, we can sort the array with merge sort (runs at $\Theta(n \lg n)$ time) and then for each element $S[i]$ in the array, we can do a binary search for $x - S[i]$ on the sorted array (this will again run at $\Theta(n \lg n)$ time). So, the overall algorithm will also run at $\Theta(n \lg n)$ time.

Pseudo-code for SUM_SEARCH(S, n, x)

See chapter text for pseudocode for MERGE-SORT and Exercise 2.3-5 for BINARY-SEARCH (we can use either of iterative and recursive binary search).

This problem can be solved in another way which still uses a $\Theta(n \lg n)$ sorting procedure but we can simplify the searching procedure to reduce the contstants in the runtime complexity.

Pseudo-code for SUM_SEARCH(S, n, x)