The Algorithm Design Manual Second Edition

Stop and Think: Finding the Intersection

Problem: Give an efficient algorithm to determine whether two sets (of size m and

n, respectively) are disjoint. Analyze the worst-case complexity in terms of m and

n, considering the case where m is substantially smaller than n.

Solution:

At least three algorithms come to mind, all of which are variants of

sorting and searching:

• First sort the big set – The big set can be sorted in O(n log n) time. We can

now do a binary search with each of the m elements in the second, looking

to see if it exists in the big set. The total time will be O((n + m) log n).

• First sort the small set – The small set can be sorted in O(m log m) time. We

can now do a binary search with each of the n elements in the big set, looking

to see if it exists in the small one. The total time will be O((n + m) log m).

• Sort both sets – Observe that once the two sets are sorted, we no longer

have to do binary search to detect a common element. We can compare the

smallest elements of the two sorted sets, and discard the smaller one if they

are not identical. By repeating this idea recursively on the now smaller sets,

we can test for duplication in linear time after sorting. The total cost is

O(n log n + m log m + n + m).

So, which of these is the fastest method? Clearly small-set sorting trumps big-

set sorting, since log m < log n when m < n. Similarly, (n + m) log m must be

asymptotically less than n log n, since n + m < 2n when m < n. Thus, sorting the

small set is the best of these options. Note that this is linear when m is constant

in size.

Note that expected linear time can be achieved by hashing. Build a hash table

containing the elements of both sets, and verify that collisions in the same bucket

are in fact identical elements. In practice, this may be the best solution.

---

4 . 2

P R A G M A T I C S O F S O R T I N G