CS 3341, Recitation Section, Problem list 4.  For Feb 10, 12.

Work on Problem 10 of Section 4.2 (page 133),
the "Nuts-and-Bolts Problem".

Here is a better statement of the problem:

   We wish to sort a bag of n nuts and n bolts by size
   in the dark.  We can compare the sizes of a nut and a
   bolt by attempting to screw one into the other.
   This operation tells us that either 
      - the nut is bigger than the bolt,
      - the bolt is bigger than the nut, or
      - they are the same size (and so fit together).
   Because it is dark we are not allowed to compare
   nuts directly or bolts directly.
   How many fitting operations do we need to sort the
   nuts and bolts?  (Average case and worst case.)

[Notice that this is in the section on quicksort.
You must follow the rules as stated in the problem.
In particular, you cannot compare two bolts or two nuts.
For simplicity, you may assume all the sizes of bolts are
different, and that each bolt has a matching nut.]

First try an order n^2 brute-force approach.

Then work out an order n*log(n) approach.

Under what circumstances will your last algorithm
still execute in time order n^2?