1
$\begingroup$

I have two array of the same set of elements, say for exemple: $a_1 = [x_1, x_2, …, x_n]$ and $a_2 = [y_1, y_2, …, y_n]$ so that $i \neq j \Rightarrow x_i \neq x_j$

Is it possible, in linear time, to construct the array $[(x_1, k_1), (x_2, k_2), …, (x_n, k_n)]$ so that $y_{k_i} = x_i$ ?

I found that with dictionnaries, I can get $O(n)$ in average and $O(n^2)$ in worst (hashtable) or $O(n\log n)$ in average and worst (balancing trees), but can't find a way to make it $O(n)$ in worst case.

We can suppose that the $x_i$ objects are integers, since it could represent memory pointers.

I found that it is possible if the set is $[\![1, n]\!]$ (just construct the array directly).

Thanks for your help.

$\endgroup$
13
  • 2
    $\begingroup$ Not if your only conditional tests use comparisons between numbers, since that would enable you to sort a permutation of $1, \dots, n$ contained in $y$ in $O(n)$ time using only comparisons, which violates a known $O(n \log n)$ lower bound in this model. $\endgroup$ Apr 10, 2018 at 16:11
  • 2
    $\begingroup$ There is a simple $O(n\log n)$ algorithm: sort both lists, keeping track of the resulting permutations, and compose them. $\endgroup$ Apr 10, 2018 at 16:15
  • 1
    $\begingroup$ You have to specify what operations you're allowed to do with your elements. Without specifying a model of computation, it is impossible to prove a lower bound. As an extreme example, if all you're allowed to do is to compare two elements for equality, then it should not be difficult to prove a strong lower bound. $\endgroup$ Apr 10, 2018 at 16:33
  • 2
    $\begingroup$ If you can only do equality test, then the same argument that shows comparison-based sorting requires $\Omega(n\log n)$ comparisons also applies here (since there are $n!$ different outcomes). However, I believe that it should be possible to prove a stronger lower bound of $\Omega(n^2)$ in this case. $\endgroup$ Apr 10, 2018 at 16:43
  • 1
    $\begingroup$ Going in the other direction, counting sort shows that there is an $O(n)$ solution if the set is a subset of $\{1,\ldots,cn\}$ for some constant $c$. Using ideas from radix sort, you can probably improve this to $\{1,\ldots,n^c\}$. $\endgroup$ Apr 10, 2018 at 16:45

2 Answers 2

2
$\begingroup$

Given the following assumptions:

  1. Since the meaning of the $=$ operator was not defined, we assume

$i≠j⇒x_i≠x_j$

...

The $x_i$ values are not necessarily integers or string, but any type of elements.

are taken to mean that each element of the set simply has a different encoding i.e. is represented by a different number in memory, and that each element is a single word, perhaps a distinct pointer to some arbitrary object.

  1. We assume that, given an arbitrary address, reading/writing at that address takes constant time.

  2. We assume that adding 2 addresses takes constant time.

  3. We assume that a pointer to unbounded memory is available in n time.

Assumptions 2 through 3 hold in most modern system, up to the memory capacity of the system. 4 only considers this program's logical space.

Then:

Consider the following construction (pseudocode). Note the time complexity, marked by "--":

//Arrays are indexed starting at 1.
//"*x = y" denotes "store y at the address pointed to by x"
//"x = *y" denotes "store the value, at the address pointed to by y, to x"

//Given:
input a1        //pointer to array a1
input a2        //pointer to array a2
input n         //number of elements in set
input mem       //address of unbounded hash table
                  //in the sense of a multitape Turing Machine, 
                  //this points to the first address on "another tape"
output result   //address of n-length array of Tuples

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    hashkey = mem + a2[t] //find an address for this element; is unique
                          //since each element is unique
    *hashkey = t;         //store the index $k_i$ at this address
}

//mem is now a pointer to a (collision free) hash table

for (t=1; t<=n; t++) { //all instructions in here are O(1) time, so
//--takes O(n) time
    k = *(a1[t])
    *(result[t]) = Tuple(a1[t], k)
}

return result

...yes this dodges the question by using the suspicious "unbounded hash table". We could be pedantic and argue that the hash table is not technically unbounded on any system we might use, but by this same pedantry we can argue that the lower time complexity bounds of every non-trivial parameterized problem is $O(∞)$ just because we can choose parameters that happen to be too large for the system's address space.

The time complexity of the algorithm, address space permitting, is thus bounded by $T(2n) ∈ O(n)$.

$\endgroup$
4
  • $\begingroup$ I think I get the idea, but can we guarantee that the memory address hashkey is not already used? Thanks for the answer. $\endgroup$
    – Nathaniel
    Apr 11, 2018 at 18:34
  • $\begingroup$ @Nathaniel Yes, this can be guaranteed, although how so depends on the architecture. I used the example of a multi-tape Turing Machine, but for an example with constant read/write time, an architecture that allows page-swapping would work just as well, i.e. hashkey refers to an address on a dedicated memory page with the same address size as the system's data size. Ultimately it's just a matter of the system having enough memory. $\endgroup$ Apr 13, 2018 at 6:29
  • $\begingroup$ Whether this works or not depends on intricacies of the computation model. As an example, how large pointers are allowed to be. $\endgroup$ Apr 13, 2018 at 22:33
  • $\begingroup$ @YuvalFilmus True. Of course, any pointer size $k$ will permit this solution in $O(n)$ time for $n$ bounded by $O(log(k))$, which is the case for pretty much any problem for which an upper bounds might be assigned and has memory complexity $ω(1)$. $\endgroup$ Apr 15, 2018 at 13:21
2
$\begingroup$

For the record, here is an $\Omega(n^2)$ lower bound when your only access to the data is using queries of the form "$x_i = y_j$?". The proof uses an adversary argument. We will assume for convenience that $n$ is divisible by $8$.

We will maintain a bipartite graph, initially with $n$ nodes on each side, corresponding to $x_1,\ldots,x_n$ on one side and to $y_1,\ldots,y_n$ on the other. There is an edge connecting $x_i$ to $y_j$ if the algorithm hasn't found out that $x_i$ is different from $y_j$. Initially, the graph is complete. If we answer a query of the algorithm by $x_i \neq y_j$ (we will soon discuss our answering strategy), then we simply remove the edge $(x_i,y_j)$. If we answer a query by $x_i = y_j$, then we remove the vertices $x_i,y_j$.

Our answering strategy will always maintain the invariant that the current bipartite graph always contains at least two perfect matchings, and so the algorithm cannot tell how to match the $x$'s with the $y$'s. We will guarantee that by ensuring that all vertices have degree at least $n/2+1$. Let us explain why this guarantees the existence of at least two perfect matchings.

First, let us show that if all vertices have degree at least $n/2$ then there is at least one perfect matching. According to Hall's theorem, there is a perfect matching if every set $S$ on the left-hand side has at least $|S|$ neighbors on the right-hand side. This is clearly satisfied when $|S| \leq n/2$. If $|S| > n/2$ then every vertex on the right-hand side is a neighbor of $S$, since otherwise it will have degree less than $n/2$.

Suppose now that all vertices have degree at least $n/2+1$. Take any vertex $v$ on the left. If we choose any of its neighbors $u$ on the right and remove both, then the remaining graph still has minimum degree at least $n/2$. Hence there is a perfect matching in which $v$ is matched to $u$. Since $v$ has at least two neighbors, this shows that there are at least two different perfect matchings.

We now describe our answering strategy. The strategy proceeds in phases, starting with phase $0$. We move to next phase after each time we answer a query by $x_i = y_j$. We will maintain the invariant that in phase $t$, all vertices have degree at least $(3/4)n-t$. This implies that all vertices have degree at least $n/2+1$ as long as $t < n/4$.

Suppose that the algorithm asks "$x_i = y_j$?" during phase $t$. If both $x_i$ and $y_j$ have degree larger than $(3/4)n-t$, then we answer $x_i \neq y_j$. This clearly maintains the invariant. If one of them has degree exactly $(3/4)n-t$, then we answer $x_i = y_j$, and proceed to phase $t+1$. This also maintains the invariant, since we have decreased each degree by at most $1$.

As we have shown above, the algorithm cannot stop until reaching phase $n/4$, since in every earlier phase there are at least two perfect matchings consistent with the known information. It remains to lower bound the number of queries needed to reach phase $n/4$. We will actually lower bound the number of queries needed to reach phase $n/8$. In order to reach phase $t$ from phase $t-1$, the degree of some vertex $v_t$ must reach $(3/4)n-t \leq (3/4)n$. So in order to reach phase $n/8$, the degree of $n/8$ vertices $v_1,\ldots,v_{n/8}$ needs to reach $(3/4)n$ or below.

The degree of a vertex can be decreased in two ways. When the algorithm answers $x_i = y_j$, the degrees of the neighbors of $x_i,y_j$ decrease by $1$; let us call this a major decrease. When the algorithm answers $x_i \neq y_j$, the degrees of $x_i,y_j$ decreases by $1$; let us call this a minor decrease. Since there are $n/8$ major decreases up to phase $n/8$, they can reduce the degree of $v_1,\ldots,v_{n/8}$ by at most $n/8$ each. Each of these vertices has to have its degree reduced using minor decreases by at least $n/8$. Since each minor decrease affects two vertices, there must be at least $(n/8)^2/2 = \Omega(n^2)$ minor decreases. In other words, the algorithm must make at least $\Omega(n^2)$ many queries.

Conversely, the problem can be solved using $\binom{n}{2} \leq n^2/2$ queries, by finding the correct match for the vertices on the left side one by one. Is this algorithm optimal? This is an interesting question for future work.

$\endgroup$

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.