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)?
Last edited by pouncer; 09/02/11 02:07 PM.