TADM2E 4.6
From Algorithm Wiki
subtract n from the first set, sort both sets in O(nlogn). find the first equal under n
One more approach to solve the above problem
1. Sort S1; (n log n)
2. Sort S2; (n log n)
3. beg := S1[0]
end := S2[m-1]
4. while (beg < n && end >=0 ) O(n)
if S1[beg] + S2[end] > sum then end--
else if S1[beg] + S2[end] < sum beg++
else return (beg, end)
End Loop
Thus overall complexity O(n log n) + O(n log n) + O(n) = O(n log n)
--Max 07:04, 25 June 2010 (EDT)
A third approach
1. Sort S1; O(n log n)
2. for i=0 to n-1
val := x - S2[i]
if binary_search(S1, val) O(log n)
return (val, S2[i])
End Loop
Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)
