## Matching Nuts and Bolts - Solution

Suppose that there are `n` nuts and bolts. A simple modification
of Quicksort shows that there are randomized algorithms whose expected
number of comparisons (and running time) are O(n log` n`): pick
a random bolt, compare it to all the nuts, find its matching nut and compare
it to all the bolts, thus splitting the problem into two problems, one
consisting of the nuts and bolts smaller than the matched pair and one
consisting of the larger ones. Repeating in this manner yields an algorithm
whose expected running time can be analyzed by imitating the known analysis
for Quicksort (see, e.g., the book by Coreman, Leiserson and Rivest, **Algorithms,
**MIT Press, 1990.) showing that it is O(`n` log `n`).

Is this the best possible? There are `n!` possibilities for matching
the nuts and bolts a priori. Every attempted matching between a nut and
a bolt has three possible outcomes (they match, the nut is larger, the
nut is small). Therefore the *information theoretic lower bound *shows
that any bounded degree decision tree that solves the problem has depth
at least log (`n!`)= Theta (`n` log` n`). This is
a lower bound for the expected number of comparisons in any *randomized
*algorithm for the problem as well.

The nuts and bolts matching problem was invented by G. J. E. Rawlins
who gives it as an exercise in his book **Compared to what? an introduction
to the analysis of algorithms,** Computer Science Press, 1991, on page
293. He gives the above outlined solution.

What about deterministic algorithms? They seem more difficult to find.
In fact, even obtaining an o(n^2) algorithm appears to be a non-trivial
task. Here is a paper (Postscript,
gzipped Postscipt) by Noga Alon,
Manuel Blum, Amos Fiat, Sampath Kannan, Moni Naor and Rafi Ostrovsky
(appeared in SODA 94) that describes an almost asymptotically
optimal deterministic algorithm. Recently, Janos Komlos, Yuan Ma and Endre
Szemeredi found a deterministic O(n log n) algorithm (appeared in SODA
96 ).

Back to the Matching Nuts and Bolts puzzle

Back to
the Puzzler page