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.
