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.