Hi guys,

Given a set of numbers and a number n, find if there are 2 numbers in the set that add up to n. (O(n lgn) time) is optimal, n^2 is the simple answer.

Firstly, how is n^2 the simple answer?

Say we have these set of numbers (total numbers = n = 4)

1 2 3 4 - find two numbers that will add up to 7

For the maximum number of possible comparisons.
1 + 2,
1 + 3,
1 + 4

2 + 1,
2 + 3,
2 + 4

3 + 1,
3 + 2,
3 + 4

4 + 1,
4 + 2,
4 + 3

That's 12 comparisons, so can anyone see where n^2 has come from? It seems like its actually O(n^2 - n)

Also, anyone see how could we optimize this so the time complexity is O(n logn)?

ah, homework time again.

if i remember correctly, O(f(n)) is the same as O(f(n) + g(n)) if g is a lower order function than f. thus O(n^2 - n) is effectively O(n^2). look at the definition of big O notation again, i'm sure this result follows directly from it.

as for the optimal solution, i can think of one that has time complexity O(n) but also space complexity O(M) where M is the number you wish to sum to.

using your example, given a[4] = {1, 2, 3, 4}, initialize an array b[7] to all 0s. then loop from i = 0 to 3, set b[a[i]] = 1. then loop again, this time checking if (b[7 - a[i]] == 1). if true, then you've found 2 numbers that add up to 7 (namely a[i] and (7 - a[i])). of course, this solution only works if you're dealing with integers and those integers are bounded. and you'll have to go through some additional pains if you plan to handle negatives.

i can't really think of a reasonable solution that runs in O(n * log(n)). perhaps something involving an initial sort?

yes, eg sort the array, then for each x in the array use binary search to test for the presence of M-x

O(n * log(n))

Isn't O(n) (what jaytea posted) better than that though?

It is indeed, as long as you can afford the space and your set of numbers consists of integers only (the O(nlogn) solution works with real numbers as well).

yup, good point! Thanks alot guys.