Set Intersection Problem

Input: 2 sets of positive integers presented as arrays $A = [a_{1},a_{2},\ldots,a_{n}]$ & $B =[b_{1},b_{2},\ldots,b_{n}]$
Question: Is there a non-empty intersection?
Output: $[i, j]$ such that $a_{i} = b_{j}$ if it exist

We want the upper and lower bounds. Make them as tight as possible.

Upper Bound:

  1. Sort A in increasing order 
  2. Sort B in increasing order 
  3. "Merge" A & B 
By merging, we mean the following algorithm

Check if $a_{1} = b_{n}$ or $a_{1} > b_{n}$ or $a_{1} < b_{n}$.

If $a_{1} = b_{n}$ then we are done.
If $a_{1} > b_{n}$ then proceed by checking if $a_{1} = b_{n-1}$ or $a_{1} > b_{n-1}$ or $a_{1} < b_{n-1}$.
If $a_{1} < b_{n}$ then proceed by checking if $a_{2} = b_{n}$ or $a_{1} > b_{n}$ or $a_{1} < b_{n}$.

Sorting takes $O(n\lg{n})$ steps. The "merging" part takes $2n-1$ steps on the worst case scenario. So the total number of steps to solve the problem is $$O(n\lg{n}) + O(n\lg{n}) + 2n-1$$ $$= O(n\lg{n})$$

Lower Bound:
Oracle decides on an ordering of the form:
$$a_{i_{1}} \le b_{j_{1}}\le a_{i_{2}}\le b_{j_{2}}\le\ldots\le b_{j_{n}}$$
Oracle answers $<$ or $>$ all questions consistently with the ordering above until the algorithm outputs an answer. If the algorithm answers NONE and one of these test is not made then Oracle says $=$.



PISIKA Copyright © 2009