Asymptotic lower bound on the number of comparisons needed to find the intersection of unsorted arrays
I think we can prove that $O(n)$ time is not attainable for the special case $k=2$, using an adversary argument.

Fix a constant $c&gt;0$.  Let's take two lists of $n$ items, where the resulting $2n$ items are all different.  Consider an algorithm that has done $cn$ comparisons between the $2n$ items in the two lists.  This defines a partial order $\preceq$ on the $2n$ items, where if the algorithm has compared $x,y$, we have either $x \prec y$ or $y \prec x$, and where we let $\preceq$ be the reflexive, antisymmetric, transitive closure of $\prec$.

I'm pretty sure that, with high probability over the choice of the lists, there exists some item $x$ in the first list and some item $y$ in the second list such that $x,y$ are incomparable under $\preceq$.  (This needs proof; I'll let you fill this part in.)

Now we can consider a parallel universe where everything is exactly the same as before, except that in the alternate universe, $y=x$.  This alternate universe is also compatible with all of the comparisons that have been made by the algorithm.  Thus, the algorithm cannot distinguish these two universes, so it must produce the same output in both cases.

However, the correct output for the two universes differs.  The correct output in the first universe is the empty set, while the correct output in the second universe is the element $\{x\}$.  Consequently, the algorithm must be incorrect in at least one of these two universes.  In other words, for at least one of these two inputs, the algorithm produces the wrong output.

It follows that, when $k=2$, any $O(n)$-time algorithm must produce an incorrect answer on at least one input.  In other words, any correct algorithm must take $\omega(n)$ time.