5
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
7
$\begingroup$

Take one random nut and try it on all screws. This (a) finds the screw for this particular nut (b) divides the set of screws into screws bigger/smaller than the nut. Now test all nuts against the screw that fits to our chosen nut. Then we have split the set of nuts and screws into two disjoint sets of screws/nuts that are smaller/larger than the first pair we found, and we can repeat the same algorithm to each of the two sets of screws and nuts.

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.

Improve this answer
$\endgroup$
7
  • $\begingroup$ 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)$. $\endgroup$
    – msh210
    Jun 7 at 14:09
  • $\begingroup$ @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$. $\endgroup$
    – Jaap Scherphuis
    Jun 7 at 14:44
  • $\begingroup$ @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? $\endgroup$
    – msh210
    Jun 7 at 16:34
  • $\begingroup$ I think: no. This is standard language for complexity estimations of algorithms. $\endgroup$
    – daw
    Jun 7 at 19:31
  • $\begingroup$ Note that to be explicit, you should specify that you take a random nut to start with - quicksort's O(n log n) running time holds on average over those random choices. $\endgroup$
    – isaacg
    Jun 7 at 21:02

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.