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