9
$\begingroup$

Consider the following problem:

Input: lists $X,Y$ of integers

Goal: determine whether there exists an integer $x$ that is in both lists.

Suppose both lists $X,Y$ are of size $n$. Is there a deterministic, linear-time algorithm for this problem? In other words, can you solve this problem in $O(n)$ time deterministically, without using randomness?

Unfortunately, you cannot assume that the list elements are all small.

I can see how to solve it in $O(n)$ expected time using a randomized algorithm: randomly choose a 2-universal hash function $h$, store the elements of $X$ into a hashtable (using $h$ as the hash function), and then look up each element of $Y$ to see if it is in the hashtable. The expected running time will be $O(n)$. However, I can't see how to find a deterministic algorithm with $O(n)$ running time. If you try to derandomize this and fix a single specific hash function, there will exist a worst-case input that causes this procedure to run in $\Theta(n^2)$ time. The best deterministic algorithm I can find involves sorting the values, but that won't be linear-time. Can we achieve linear running time?

Also, I can see how to solve it in linear time if you assume that all of the list elements are integers in the range $[1,n]$ (basically, do counting sort) -- but I am interested in what happens in the general case when we cannot assume that.

If the answer depends on the model of computation, the RAM model jumps to mind, but I'd be interested in results for any reasonable model of computation. I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model.

Improve this question
$\endgroup$
4
  • $\begingroup$ Hashtables are O(n log n) as you need to handle collisions. $\endgroup$
    – Thorbjørn Ravn Andersen
    Feb 5, 2015 at 0:45
  • 1
    $\begingroup$ @ThorbjørnRavnAndersen, I'm not seeing where you are getting that from. Using 2-universal hash functions and a suitably-sized hash table ensures that the number of hash collisions is minimal (with high probability), so I believe $O(n)$ running time is achievable. I'm not sure where you got $O(n \lg n)$ from; if you don't do something special (like use 2-universal hashing), the worst case is $O(n^2)$, due to collisions. $\endgroup$
    – D.W. ♦
    Feb 5, 2015 at 1:12
  • $\begingroup$ The devil is in the detail, here a "suitably sized hash-table". This might turn out to be pretty big, if you do not want collisions. The typical n-log-n is (if I recall correctly) for handling the hash function collisions with a list. $\endgroup$
    – Thorbjørn Ravn Andersen
    Feb 5, 2015 at 1:16
  • 1
    $\begingroup$ @ThorbjørnRavnAndersen The expected number of keys mapping to the same address is constant (for tables that are not overloaded), so the kind of collision resolution is irrelevant. See also here. $O(n \log n)$ fits the worst case if you use (external) balanced BSTs instead of lists. $\endgroup$
    – Raphael ♦
    Feb 5, 2015 at 7:33

4 Answers 4

Reset to default
1
$\begingroup$

You can solve the problem in linear time if you have enough memory to have a bit for each possible value in X and Y. This does not impose any restrictions of the ordering of X and Y.

  1. Initially all bits are unset.
  2. Iterate over X setting the corresponding bit.
  3. Iterate over Y checking if the corresponding bit was set above.
Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ Unfortunately, you cannot assume that all of the integers are small (you can't assume they are small enough that this algorithm will work). In the general case, the running time of this algorithm will be exponential in the bit-length of the list elements. Thank you, though! $\endgroup$
    – D.W. ♦
    Feb 5, 2015 at 1:11
  • $\begingroup$ Let's name it a "suitably sized bit-array" then. Also linear in the bit-length is equivalent to log-n. Are you serious about getting log-n performance without any restrictions or preconditions on the input data? $\endgroup$
    – Thorbjørn Ravn Andersen
    Feb 5, 2015 at 1:19
  • 2
    $\begingroup$ @ThorbjørnRavnAndersen The space is exponential in the bit length (you need to map from all possible values), and the time is linear in the total list size (you need to look at all values in both lists). Nothing is linear in the bit-length. $\endgroup$
    – wchargin
    Feb 5, 2015 at 3:36
0
$\begingroup$

Since you are saying that the two lists contain integers, I guess we can run a radix sort on the two lists and then do a linear search comparing the two lists for equivalent items.

Improve this answer
$\endgroup$
4
  • 4
    $\begingroup$ This only works if there is a bound on the magnitude of the numbers. $\endgroup$
    – Luke Mathieson
    Feb 5, 2015 at 6:36
  • $\begingroup$ but I thought high magnitude will be a problem only for counting sort and for radix sort we can select a high enough radix to solve that problem... please let me know what I'm missing here $\endgroup$
    – anirudh
    Feb 5, 2015 at 9:54
  • $\begingroup$ What if one of the numbers is 2^(2^128)? $\endgroup$
    – miniBill
    Feb 5, 2015 at 21:13
  • $\begingroup$ @anirudh but then you have a different algorithm for different input sizes - you need a bigger alphabet each time you increase the radix, you're just exporting the complexity of increasing magnitude to increasing the alphabet size. Of course this is only possible in theory as well, I don't think a lot of hardware allows you to change which base it represents numbers in (we can pretend at the input and output ends, but it boils down to (mostly) binary). $\endgroup$
    – Luke Mathieson
    Feb 5, 2015 at 23:43
0
$\begingroup$

Why not insert the integers of each list into a simple bitwise trie? Would this not be optimal, in the sense that it is $\mathcal O\left(n\cdot \overline m\right)$, where $\overline m$ is the average bit size of the integers; specifically, I do not see how you can do better, as simply *reading* the two lists would take this amount of time.

Improve this answer
$\endgroup$
4
  • $\begingroup$ Thanks for your note. See the last paragraph of the question, which addresses this point. In the RAM model, you can read the two lists in $O(n)$ time -- it doesn't take $O(n \cdot \overbar{m})$ time. So that's where the model of computation comes into it -- this answer doesn't actually prove that deterministic linear time is impossible. $\endgroup$
    – D.W. ♦
    Apr 13, 2016 at 19:23
  • $\begingroup$ @D.W. In the RAM model, there is a word size $w$ which is a constant, and it bounds $m$ and thus also $\overline{m}$, which results in a runtime of $\mathcal O\left(n\right)$, or am I mistaken? $\endgroup$
    – Realz Slaw
    Apr 13, 2016 at 19:28
  • $\begingroup$ hmm maybe considering $w$ a constant is a mistake. $\endgroup$
    – Realz Slaw
    Apr 13, 2016 at 19:32
  • $\begingroup$ ($w$ is not considered constant, but dependant on $n$: you can have it any constant multiple $m$ of what is necessary to represent $n$ (wide enough to represent $n^m$), just not arbitrarily large.) $\endgroup$
    – greybeard
    Apr 14, 2016 at 4:45
-1
$\begingroup$

It is similar to the Elemet Uniqueness problem, where you have a set of n numbers and you want to determine whether all of the elements are distinct. The problem has an algebraic computation tree lower bound of $O(n\log n)$.

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ The question is quite explicit about linear deterministic time, not log-linear. Also to determine if (not on what value) set has only unique elements you can do faster than loglinear. $\endgroup$
    – Evil
    Apr 13, 2016 at 18:16
  • 1
    $\begingroup$ Do you mean $\Omega(n\log n)$? If so, that might suggest that the problem in the question can't be solved in linear time. But just saying that a related problem can be solved in log-linear time doesn't really answer the question. (cc @EvilJS) $\endgroup$
    – David Richerby
    Apr 13, 2016 at 19:06
  • 1
    $\begingroup$ Thanks for your note. I wonder if you missed the last sentence of the question. I'll repeat it here: "I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model." In other words, this answer doesn't answer the question; it merely repeats something that I already said in the question I was aware of, but which doesn't resolve the question. $\endgroup$
    – D.W. ♦
    Apr 13, 2016 at 19:24
  • $\begingroup$ It can be done in $O(n \log \log n)$ time which is better than given $O(n \log n)$, so I am sure this was not $\Omega(n \log n)$, but this does not solve the D.W. question. So just comment here. $\endgroup$
    – Evil
    Apr 13, 2016 at 22:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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