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

Question

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 complexity for finding one common element?

Because, once a common element is found, the second problem can be solved in linear time.

---

Edit

The algorithm(s) that I thought are pretty simple:

For problem 1: Build two heaps for $A$ and $B$(which takes linear time and can be done in-place), then compare the minimum of the heaps, if they match print it and remove both, otherwise remove the smallest one and continue until the heaps are empty(this clearly takes $O((m\log(m) + n\log(n)) = O(\max(m,n)\log(\max(m,n)))$).

An other solution is to sort one array in-place, scan the other array and use bisection search to find matches. If we sort the smallest array (with size $m$) then the complexity is $O(m\log(m) + n\log(m)) = O(\max(m,n)\log(\min(m,n)))$. This technique yields the values in the other in which their are found in the biggest array, and it can be used to solve the second problem.

But, as you can see, I'm not using the extra restrictions at all and both algorithms use $O(1)$ space instead of $O(k)$(yes, it's still constant but $O(k)$ should give a bit more freedom).

Answer 1

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.