# Time complexity of set intersection

This problem involves the time-complexity of determining set intersections, and the algorithm must give output on all possible inputs (as described below).

Problem 1: The input is a positive integer $m$, and two unordered subsets $A$ and $B$ of $\{1,\dots,n\}$. The size of the input is $n+ |A| +|B|$.

Output: The set $A \cap B$, the intersection of $A$ and $B$.

As all infinitely many possibilities are ranged through, with the size of output $n = m + |A| + |B|$, is there a linear-time algorithm that on any $(n,A,B)$, outputs $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients? (Worst-case complexity.)

Problem 2: The input is a positive integer $m$, and $j$ unordered subsets $A_1, \dots, A_j$ of $\{1,\dots,n\}$. The size of the input is $n+ |A_1| + \cdots + |A_n|$.

Output: $A_1 \cap A_2 \cap \cdots \cap A_n$, the intersection of $A_1, \dots, A_j$.

As all infinitely many possibilities are ranged through, with the size of output $n = m + |A| + |B|$, is there a linear-time algorithm that on any $(n,A,B)$, outputs $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients? (Worst-case complexity.)

Are there references to the time complexity of these problems? I’m interested in the particular algorithms themselves, but if anyone knows that complexities above are linear-time or $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients, I’d be grateful to hear from you. ( I’m less interested in algorithms that involve hash functions, but as long as such an algorithm works on all possible inputs, a hash function algorithm is okay.) I’m not a computer scientist student but an older person learning things as they come along in work-in-progress.

• This sounds like homework. Please tell us what you tried. For problem 1, could you clarify what is $m$? Assuming $m$ is extraneous, you can tell we need to at least read the entire input (worst case)? It seems you can check existence of each $i \in \{1, \ldots, n\}$ in constant time - what does that tell you about the overall complexity? Problem 2 builds on problem 1 in a straightforward way – Reinstate Monica Aug 6 '18 at 1:45
• You seem to have mixed up $n$ and $m$. You also seem to have copied some text from Problem 1 to Problem2. Finally, note that you actually have two questions. The usual rule is one question per post. – Yuval Filmus Aug 6 '18 at 1:49

There is a simple $O(n)$ algorithm for computing $A \cap B$, which involves an array of length $n$.

Another algorithm sorts $A \cup B$ to find the intersection in time $O(n\log n)$. In contrast to the previous algorithm, this algorithm can be implemented using only comparisons. There is a matching $\Omega(n\log n)$ lower bound in the algebraic decision tree model; see for example lecture notes of Otfried Cheong.

• I'm not a student, nor have been for 30+ years.... Thank you for the answer to the first question... I take it that O(n) algorithm would involve hash sets, or some more advance methods than comparisons? Thanks again--Steven (I'll post my second question as a single question.) – Steven48 Aug 6 '18 at 2:14
• There is absolutely no need for any hash. The elements are already in the range $1,\ldots,n$, and can function as their own hash. – Yuval Filmus Aug 6 '18 at 2:15
• What then would O(n) look like? I get the O(n log n) one [put sets into one array, order, find elements that repeat], but have no idea at all how to do O(n). [Mathematician, old 70, working on something involving time complexity...learning.] – Steven48 Aug 6 '18 at 2:17
• The only way to learn is to solve exercises. There's no point in my spelling out the answer. – Yuval Filmus Aug 6 '18 at 2:18

You can’t give the time complexity because a set is not a primitive data structure, so you need to know how it is represented.

Why would n be part of the input size? Let A = { 1,000,000,000 } and B = { 1, 1,000,000,000 }, for example.

• We want to measure resource consumption in terms of $n$ rather than in terms of the input length. This allows us to compute the intersection of $A$ and $B$ in linear although the actual running time is $\Theta(n)$. – Yuval Filmus Aug 6 '18 at 13:13