On the Number of Comparisons to Find the Intersection of Two Relations
Larry J. Stockmeyer, C. K. Wong · SIAM Journal on Computing · 1979
Given two finite sets of k-tuples whose component elements are drawn from an infinite totally ordered set, the problem of identifying the k-tuples which belong to both sets is considered. Attention is restricted to algorithms that perform pairwise comparisons on the component elements of the k-tuples. If the two sets have cardinalities m and n with $m \leqq n$ it is shown that, in the worst case, \[ (m + n) \cdot \log _2 m + (m + n - 1)k \] comparisons are sufficient and \[ \max ((m + n) \cdot \log _2 m - 2.9m,(m + n - 1)k) \] comparisons are necessary. Upper and lower bounds are also given for the number of comparisons required to recognize duplicate tuples in a sequence of tuples, and to determine the lexicographic order of a sequence of tuples. In all cases, the disparity between the upper and lower bounds is at most a factor of two asymptotically.