# 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 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).

• If you want to use it in real work (software development, ....), just hash them and find common elements (most hashing algorithm are false positive but this happens very rarely), otherwise as Yuval said you reading too much into this. – user742 May 22 '13 at 19:16
• @SaeedAmiri I'm not interested in using this in real work, I just wanted to know whether there was a know lower-bound for the worst case. And, yes I'd definitely use hashing if it were for real work. – Bakuriu May 22 '13 at 20:28

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.)
• I've added a brief description of the algorithms I devised. Modifying input arrays is allowed. I'll look into the link you posted, thank your. Regarding the second problem, the restriction on the constant $k$ makes me think that something like counting-sort could be possible, but I really see no way to use it in that sense. Am I right that comparison based approaches are the only sensible ones in both problems? – Bakuriu May 22 '13 at 7:17