### Abstract

The problem of matching nuts and bolts is the following: Given a collection of n nuts of distinct sizes and n bolts such that there is a one-to-one correspondence between the nuts and the bolts, find for each nut its corresponding bolt. We can only compare nuts to bolts. That is we can neither compare nuts to nuts, nor bolts to bolts. This humble restriction on the comparisons appears to make this problem very hard to solve. In fact, the best explicit deterministic algorithm to date is due to Alon et al. (1994) and takes Θ(n log^{4}) time. In this paper, we give a simpler O(n log^{2} n) time algorithm. The existence of an O (n log n) time algorithm has been proved recently (Bradford, 1995; Komlós et al., 1996).

Original language | English (US) |
---|---|

Pages (from-to) | 123-127 |

Number of pages | 5 |

Journal | Information Processing Letters |

Volume | 59 |

Issue number | 3 |

DOIs | |

State | Published - Aug 12 1996 |

Externally published | Yes |

### All Science Journal Classification (ASJC) codes

- Theoretical Computer Science
- Signal Processing
- Information Systems
- Computer Science Applications

### Keywords

- Analysis of algorithms
- Nuts and bolts
- Sorting

## Fingerprint Dive into the research topics of 'Matching nuts and bolts faster'. Together they form a unique fingerprint.

## Cite this

*Information Processing Letters*,

*59*(3), 123-127. https://doi.org/10.1016/0020-0190(96)00104-4