4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – user742 May 22 '13 at 19:16
  • $\begingroup$ @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. $\endgroup$ – Bakuriu May 22 '13 at 20:28
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Bakuriu May 22 '13 at 7:17
  • 1
    $\begingroup$ In the second problem you have to output the common elements in the order that they appear in the arrays, rather than sorted. Perhaps that's where the difference comes from. $\endgroup$ – Yuval Filmus May 22 '13 at 7:31
  • $\begingroup$ Yes, but I cannot see how to use this fact. I mean, once you find a common element you are done in the second problem, since you can find all the others in linear time(considering the restrictions). The problem is that I don't see how finding a single common element is different than finding all the common elements. When you consider two arrays that have only one common element the restrictions do not apply, hence you fall back to the first problem(correct?). $\endgroup$ – Bakuriu May 22 '13 at 7:34
  • 1
    $\begingroup$ The problems are different - in the first you need to output all common elements, in increasing order, while in the second you need to output all common elements, in the order that they appear in the arrays. You're right that the problems might be easy, but they are still different. $\endgroup$ – Yuval Filmus May 22 '13 at 8:53
  • 2
    $\begingroup$ Probably not, since finding whether two arrays intersect is already difficult. I think you are reading too much into these problems. $\endgroup$ – Yuval Filmus May 22 '13 at 14:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.