# Nuts and screws

Imagine that you are given a box with n nuts and n screws. Each screw have different size (diameter) and on each screw there is exactly one matching nut that fits.

How many tries on average do you need to assign each nut to a particular screw? (Try to minimize tries as much as possible)

The only operation that you can do is to try the nut on a screw and that will give you one of three results:
a) Nut is too big
b) Nut is too small
c) Nut fits

A straightforward approach would be to always pick up one nut and try all screws (worst >!possible scenario) to find the right one. So we would have to try n + n-1 + n-2 + ... + 1 screws. Which is $$\frac{n*(n-1)}{2}$$ tries.

This algorithm is nothing else than quicksort, and performs essentially double as many comparisons as quicksort. Quicksort tooks on average $$O(n\log n)$$ operations, so will this algorithm.
• But the question was "How many tries on average do you need to assign each nut to a particular screw?" so I guess the answer would be $O(\frac{n\log n}{n²})=O(\frac1n\log n)$. Jun 7 at 14:09
• @msh210 I think they're asking what the average is of the total number of tries needed to match every nut with its associated screw. This is not the average per screw or per nut. See for example the spoilered hint. That hint does however muddy the waters a bit since it is about the worst case rather than the average. BTW, if it were an average per screw or per nut, you would have to divide by $n$, not by $n^2$. Jun 7 at 14:44
• @JaapScherphuis "How many tries on average do you need to assign each nut to a particular screw?" sounds to me like you consider a specific screw, say screw number 3, and count the number of times you need to assign each nut, say nut number 5, to it. For each nut, that'll be 0 or 1 time, and the average will be (if this answer is correct) $O(\frac1n\log n)$. No? Jun 7 at 16:34