4
$\begingroup$

A project at university (whose deadline has passed by now) presented the following problem:

Consider two finite sequences of (not necessarily distinct) real numbers $a_1,\ldots,a_n$ and $b_1,\ldots,b_n$ such that the $b_k$'s are a permutation of the $a_k$'s. The aim is to create an algorithm which returns a permutation which maps the sequence $(a_k)$ onto $(b_k)$. In order to find such permutation it is necessary to compare some numbers during the algorithm. The restriction is that one cannot compare any $a_x$ with an $a_y$ or a $b_x$ with a $b_y$: all that is allowed is to compare a number of the first sequence with one of the second sequence.

I am wondering what would be the minimal (worst-case) complexity of the number of comparisons. It's not hard to get $O(n^2)$: for every $a_x$, search brute-force for a corresponding $b_y$, which costs $O(n)$ comparisons giving a total of $O(n^2)$.
A bit smarter would be to adapt the familiar QuickSort algorithm, in the recursions step taking as a pivot a couple $(a_x,b_y=a_x)$ (which can be found in $O(n)$ comparisons) and partitioning both sequences using this 'pivot'. This gives $\Theta(n\log n)$ comparisons in average, but still $\Theta(n^2)$ worst-case (as usual with QuickSort).

It's not hard to see that $\Omega(n\log n)$ is a minimum: represent a given algorithm as a binary decision tree with a comparison at each node. Since the total number of leaves can reach $\Theta(n!)$ (the number of permutations in case all the $a_k$ are different) the height of the tree is at least $\Omega(\log_2(n!))=\Omega(n\log n)$.

It seems likely that a $O(n\log n)$ algorithm exist, but I have not been able to find one. I have tried adapting MergeSort, but a problem during the merging arises giving a worst-case of $\Theta(n^2)$ nonetheless.

Is this a known problem? Does a $O(n\log n)$ algorithm exist? Do you have suggestions for other known sorting algorithms which might be adapted without increasing their complexity?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

This is the famous "nuts and bolts" problem. Yes, there is a randomized algorithm with expected running time $O(n \lg n)$, using a QuickSort-like algorithm.

The problem is famous because there is a simple randomized algorithm that achieves $O(n \lg n)$ expected running time. However, it's very challenging to find a deterministic algorithm with a $O(n \lg n)$ time running bound. Therefore, it makes a nice illustration of the utility of randomness.

The problem is described in several algorithms textbooks, including CLRS and Skienna's textbook.

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thanks. However the randomized algorithm is still $\Theta(n^2)$ in worst-case. Do you know of any deterministic algorithm with worst-case complexity $O(n\log n)$? $\endgroup$
    – user26044
    Dec 22, 2014 at 8:42
  • 1
    $\begingroup$ @barto, I encourage you to click through the link I gave you. It already answers your question -- it has a citation to such a deterministic algorithm. (P.S. For practical purposes, worst-case running time is usually not the right way to measure the performance of a randomized algorithm. I believe the probability that the randomized algorithm takes longer than $c n \lg n$ is exponentially small in $c$.) $\endgroup$
    – D.W. ♦
    Dec 22, 2014 at 19:32
  • $\begingroup$ Right, I didn't read that last sentence. The article by Komlós, Ma and Szemerédi can be read on Google Books (pg. 232) $\endgroup$
    – user26044
    Dec 22, 2014 at 19:42

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.