Lower-bound complexities for finding common elements between two unsorted arrays

I'm facing some problems that deal with finding common elements between unsorted arrays and I'd like to know whether there are well-known lower-bounds for the worst-case and, eventually, what are these lower-bounds.

The problems are pretty simple:


Given two unsorted arrays of distinct integers, $A$ and $B$, of size
$m$ and $n$, determine all the common elements between the two
arrays(the output must be sorted)

Which I believe has a lower-bound complexity of $\Omega((m+n)\log(\min(m,n)))$
(and $O(1)$ space complexity, if we exclude the input arrays),
even though I cannot find any proof of this fact. [I found an algorithm with this complexity, so I(hopefully) am not underestimating the complexity.]

The other problem adds some restrictions(and hence I'd expect to be able to lower the complexity):


Given two unsorted arrays of distinct integers, $A$ and $B$, of size
$m$ and $n$; knowing that common elements between the arrays have the
same relative order in both arrays and that for every couple of
consecutive common elements, their distance is at most $k$(constant),
determine all the common elements between the two arrays maintaining
their relative order and using at most $O(k)$ memory in addition to
the input arrays.

I've tried to think about this second problem but I cannot see how the restrictions change the complexities. What puzzles me is that I believe that finding a single couple of elements between two unsorted arrays is $\Theta((n+m)\log(\min(n,m)))$, and since this is a special instance of this second problem then the restrictions do not add anything to the problem itself.

Are my guesses correct, and if so where can I find proofs for these lower-bounds? Do the restrictions change anything at all or the solution for the first problem is the best we can achieve in both cases?

Probably my questions can be summarized by the following:


Given two arrays of distinct integers $A$ and $B$ of size $m$ and $n$,
what is the lower-bound c

For the first question, when $m = n$, you can get an easy $\Omega(n\log n)$ lower bound (in appropriate computation models) by taking $A = B$. More generally, following the method outlined here, it seems that (assuming $n \geq m$) you can get a lower bound of $\Omega(\log (m! \binom{n+1}{m})) = \Omega(n\log m)$ by considering the problem of Set Intersection. (In the proof of Theorem 4, fix the order of the $X$s, and vary the order of the $Y$s and their location.)

As for your algorithm, perhaps it modifies the input arrays? Perhaps this is not allowed in the intended computation model, in which the input is read-only, the work tape is read-write, and the output tape is write-only. (This is just a guess.) In any case, it will really help if you explained your algorithm.

StackExchange Computer Science Q#12182, answer score: 4