patternMinor
Time complexity of set intersection
Viewed 0 times
setcomplexitytimeintersection
Problem
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.
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.
Solution
Your post contains two problems. I will only address the first.
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.
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.
Context
StackExchange Computer Science Q#95996, answer score: 3
Revisions (0)
No revisions yet.