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

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 . Even in average case, this brute-force algorithm will run at time (as we have to iterate over the set for each element).

But we have to think of a -time algorithm.

TIP: Every time we see , 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 time for a sorted array.

So, we can sort the array with merge sort (runs at time) and then for each element in the array, we can do a binary search for on the sorted array (this will again run at time). So, the overall algorithm will also run at time.

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

1
2
3
4
5
MERGE-SORT(S, 1, n)
for i = 1 to n
    if BINARY-SEARCH(S, x - S[i]) != NIL
        return true
return false

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

1
2
3
4
5
6
7
8
9
10
11
12
13
MERGE-SORT(S, 1, n)
left = 0
right = n - 1
while (left < right) {
    if (S[left] + S[right] == x) {
        return true
    } else if (S[left + S[right] < x) {
        left++;
    } else {
        right--;
    }
}
return false
If you have any question or suggestion or you have found any error in this solution, please leave a comment below.