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\).

Firstly we sort \(S\) by way of MERGE-SORT which takes \(\Theta(n \lg n)\) time. We then iterate over our sorted array and use BINARY-SEARCH to determine if the integer that would sum to \(x\). BINARY-SEARCH takes \(\Theta(\lg n)\) time and doing it \(n\) times takes \(\Theta(n \lg n)\) time. Since both these steps take \(\Theta(n \lg n)\) time, combining the two of them is the same as multiplying that time by a constant factor. Therefore this algorithm runs at \(\Theta(n \lg n)\) time.