TADM2E 4.6

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 <pre> 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) </pre> --Max 07:04, 25 June 2010 (EDT)

A third approach <pre> 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

</pre>

Overall complexity is O(n log n) + O(n) * O(log n) = O(n log n)

Navigation menu