12 Apr
2019
12 Apr
'19
11:35 a.m.
= James Propp <jamespropp@gmail.com> I don't see how to do it in amortized time O(n). (For that matter, I don't see how to do O(n log n) either.) Hints? Answers? References?
For O(n log n) you can sort the two lists, then scan them in tandem. For O(n) you can put one of the lists in a hash table, then scan through the other. These days a million really isn't considered a large number, for some value of a million.