18
$\begingroup$

Consider the following problem:

Input: two arrays $A$ and $B$ of length $n$, where $B$ is in sorted order.

Query: do $A$ and $B$ contain the same items (with their multiplicity)?

What is the fastest deterministic algorithm for this problem?
Can it be solved faster than sorting them? Can this problem be solved in deterministic linear time?

$\endgroup$
  • 1
    $\begingroup$ FWIW the probabilistic approach is hashing with an order-independent hash function. Carter and Wegman wrote one of the original papers on this (sciencedirect.com/science/article/pii/0022000081900337), but I haven't seen anything in the citations of that paper that suggests a deterministic algorithm (so far). $\endgroup$ – KWillets Jan 5 '16 at 18:31
  • 1
    $\begingroup$ The statement you quote is about the Turing machine model, which is only of theoretical interest. Algorithms are usually analyzed with respect to the RAM model. $\endgroup$ – Yuval Filmus May 17 '16 at 22:27
  • $\begingroup$ ah, then that's the model I'm looking for. I adjusted the question. $\endgroup$ – Albert Hendriks May 18 '16 at 6:55
  • $\begingroup$ Why don't you just sum the items in the array and then compare the summation ? Regarding your title, it is linear and answers the question 'is one array the sorted version of other? '. I'm aware that it is not the Turing machine model, but a practical solution. $\endgroup$ – atayenel May 18 '16 at 7:17
  • 1
    $\begingroup$ @AlbertHendriks You (most probably) can't sort an array in $O(n\log n)$ on a Turing machine. Some lower bounds on SAT (e.g. cs.cmu.edu/~ryanw/automated-lbs.pdf) are actually for the RAM machine, sorry for my misleading earlier comment. $\endgroup$ – Yuval Filmus May 18 '16 at 8:44
14
$\begingroup$

You haven't specified your computation model, so I will assume the comparison model.

Consider the special case in which the array $B$ is taken from the list $$ \{1,2\} \times \{3,4\} \times \cdots \times \{2n-1,2n\}. $$ In words, the $i$th element is either $2i-1$ or $2i$.

I claim that if the algorithm concludes that $A$ and $B$ contain the same elements, that the algorithm has compared each element in $B$ to its counterpart in $A$. Indeed, suppose that the algorithm concludes that $A$ and $B$ contain the same elements, but never compares the first element of $B$ to its counterpart in $A$. If we switch the first element then the algorithm would proceed in exactly the same way, even though the answer is different. This shows that the algorithm must compare the first element (and any other element) to its counterpart in $A$.

This means that if $A$ and $B$ contain the same elements, then after verifying this the algorithm knows the sorted order of $A$. Hence it must have at least $n!$ different leaves, and so it takes time $\Omega(n\log n)$.

$\endgroup$
  • $\begingroup$ I would have thought this would imply that $P = \Omega(n\log n)$ in general, but apparently the comparison model is different with that. $\endgroup$ – Albert Hendriks Jan 5 '16 at 19:04
  • $\begingroup$ @AlbertHendriks, it is the same model used to show n lg n lower bound for sorting. It means that it the only operation you can perform is comparison then you cannot do better. I think this answers your question. $\endgroup$ – Kaveh Jan 6 '16 at 9:24
  • $\begingroup$ [Cntd] we don't have stronger bounds even for sorting! and if you can sort faster than n lg n then you can use that for solving the problem faster than n lg n. $\endgroup$ – Kaveh Jan 6 '16 at 9:26
  • 1
    $\begingroup$ @AlbertHendriks, do you know about linear time algorithms for sorting integers? Look it up in CLRS. Your case might be one of the cases where we can sort in linear time. $\endgroup$ – Kaveh Jan 6 '16 at 9:33
  • 6
    $\begingroup$ Integers can be sorted in $O(n\log\log n)$ (see nada.kth.se/~snilsson/fast-sorting), or in expected time $O(n\sqrt{\log\log n})$ (see ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1181890), or even in linear time if the word size is large enough (see LNCS 8503, p. 26ff). $\endgroup$ – Yuval Filmus Jan 6 '16 at 9:44
10
$\begingroup$

This answer considers a different model of computation: the unit-cost RAM model. In this model, machine words have size $O(\log n)$, and operations on them take $O(1)$ time. We also assume for simplicity that each array element fits in one machine word (and so is at most $n^{O(1)}$ in magnitude).

We will construct a linear time randomized algorithm with one-sided error (the algorithm might declare the two arrays to contain the same elements even if this is not the case) for the more difficult problem of determining whether two arrays $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ contain the same elements. (We don't require any of them to be sorted.) Our algorithm will make an error with probability at most $1/n$.

The idea is that the following identity holds iff the arrays contain the same elements: $$ \prod_{i=1}^n (x-a_i) = \prod_{i=1}^n (x-b_i). $$ Computing these polynomials exactly will take too much time. Instead, we choose a random prime $p$ and a random $x_0$ and test whether $$ \prod_{i=1}^n (x_0-a_i) \equiv \prod_{i=1}^n (x_0-b_i) \pmod{p}. $$ If the arrays are equal, the test will always pass, so let's concentrate on the cases in which the arrays are different. In particular, some coefficient of $\prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i)$ is non-zero. Since $a_i,b_i$ have magnitude $n^{O(1)}$, this coefficient has magnitude $2^n n^{O(n)} = n^{O(n)}$, and so it has at most $O(n)$ prime factors of size $\Omega(n)$. This means that if we choose a set of at least $n^2$ primes $p$ of size at least $n^2$ (say), then for a random prime $p$ of this set it will hold with probability at least $1-1/n$ that $$ \prod_{i=1}^n (x-a_i) - \prod_{i=1}^n (x-b_i) \not\equiv 0 \pmod{p}. $$ A random $x_0$ modulo $p$ will witness this with probability $1-n/p \geq 1-1/n$ (since a polynomial of degree at most $n$ has at most $n$ roots).

In conclusion, if we choose a random $p$ of size roughly $n^2$ among a set of at least $n^2$ different primes, and a random $x_0$ modulo $p$, then when the arrays don't contain the same elements, our test will fail with probability $1-O(1/n)$. Running the test takes time $O(n)$ since $p$ fits into a constant number of machine words.

Using polynomial time primality testing and since the density of primes of size roughly $n^2$ is $\Omega(1/\log n)$, we can choose a random prime $p$ in time $(\log n)^{O(1)}$. Choosing a random $x_0$ modulo $p$ can be implemented in various ways, and is made easier since in our case we don't need a completely uniform random $x_0$.

In conclusion, our algorithm runs in time $O(n)$, always outputs YES if the arrays contain the same elements, and outputs NO with probability $1-O(1/n)$ if the arrays don't contain the same elements. We can improve the error probability to $1-O(1/n^C)$ for any constant $C$.

$\endgroup$
  • 1
    $\begingroup$ While this algorithm is randomized, it explains how to implement the ideas in some of the other answers so that they actually work. It also has an advantage over the hashtable approach: it is in-place. $\endgroup$ – Yuval Filmus Jan 6 '16 at 10:22
  • $\begingroup$ I think the OP doesn't like probabilistic algorithms as he didn't like the expected linear time algorithm using a hash table. $\endgroup$ – Kaveh Jan 6 '16 at 10:25
  • $\begingroup$ Kaveh you're right. But of course this solution is also interesting and should be kept, it solves the case for probabilistic algorithms. Also, I think it uses the model that I'm looking for. $\endgroup$ – Albert Hendriks Jan 6 '16 at 10:27
  • 1
    $\begingroup$ I'm just wondering if the notation O(1/n) is correct. Of course I know what you mean, but I think by the definition of big-O this is equivalent to O(1). $\endgroup$ – Albert Hendriks Jan 6 '16 at 10:33
  • 2
    $\begingroup$ Not at all. It's a quantity bounded by $C/n$ for large enough $n$. That's a better guarantee than $O(1)$. $\endgroup$ – Yuval Filmus Jan 6 '16 at 10:34
-3
$\begingroup$

i will propose another algorithm (or at least a scheme of such an algorithm)

The scheme assumes the values (assumed "integers") are within a (narrow?) range between $[min,max]$

  1. In $O(n)$ time scanning the two arrays, we can find the min and max values for both and their multiplicity, if these differ, the arrays are not permutations of each other

  2. Subtract the min from all values from both arrays (here the fact that one array is already in sorted order is not taken into account, presumably this can be improved)

  3. Assume the values in the arrays represent masses and we apply an acceleration/velocity to each of magnitude $1$ (this can be improved to a magnitude of $c > 1$ under certain cases)

  4. move the masses until they reach the maximum value max-min, this has a complexity of $O((max-min)n)$. This allows to find both same values and their multiplicity, if these differ, the arrays are not permutations of each other. Else decide the arrays are permutations of each other.

note the above algorithm scheme can be (deterministicaly) quite fast in many practical situations.

The above algorithm scheme is a variation on a linear-time sorting algorithm employing "moving masses". The physical intuition behind the "moving masses" sorting algorithm is this:

Assume each item's value actually represents its mass magnitude and imagine arranging all items in a line and applying the same acceleration force.

Then each item will move up to a distance related to its mass, more massive less distance and vice-versa. Then to retrieve the sorted items simply collect the items in reverse order by distance traveled.

This algorithm is linear-time and deterministic, but there is a caveat in that the amount of initial acceleration force and distance to travel (or time to wait) is related to the distribution of values (i.e the "masses", the $max-min$ factor above). One can also try to discretize the space for the items to travel into a grid and gain a constant factor in algorithm speed (and use a fast sorting routine to sort different items in the same cell).

In this respect, the above algorithm is similar to numerical-based sorting algorithms (e.g radix-sort, counting-sort)

One may think that this algorithm might not mean much, but it shows at least one thing. That, "fundamentaly", at a physical level, sorting arbitrary numbers is a linear-time operation in the number of items.

$\endgroup$
  • $\begingroup$ In terms of collecting the items in reverse order of distance travelled, wouldn't that translate to comparisons at the implementation level, and at that point do you not have to sort the "distances"? $\endgroup$ – JustAnotherSoul May 18 '16 at 15:24

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.