# Deterministic linear time algorithm to check if one array is a sorted version of the other

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?

• 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). Jan 5 '16 at 18:31
• 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. May 17 '16 at 22:27
• ah, then that's the model I'm looking for. I adjusted the question. May 18 '16 at 6:55
• 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. May 18 '16 at 7:17
• @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. May 18 '16 at 8:44

## 2 Answers

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

• I would have thought this would imply that $P = \Omega(n\log n)$ in general, but apparently the comparison model is different with that. Jan 5 '16 at 19:04
• @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. Jan 6 '16 at 9:24
• [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. Jan 6 '16 at 9:26
• @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. Jan 6 '16 at 9:33
• 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). Jan 6 '16 at 9:44

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

• 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. Jan 6 '16 at 10:22
• I think the OP doesn't like probabilistic algorithms as he didn't like the expected linear time algorithm using a hash table. Jan 6 '16 at 10:25
• 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. Jan 6 '16 at 10:27
• 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). Jan 6 '16 at 10:33
• Not at all. It's a quantity bounded by $C/n$ for large enough $n$. That's a better guarantee than $O(1)$. Jan 6 '16 at 10:34