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 Aug 6, 2018 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. Aug 6, 2018 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.
• 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. Aug 6, 2018 at 2:15
• 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)$. Aug 6, 2018 at 13:13