How to analyze an efficient algorithm?
Posted on 2008-06-16
Bob has a set A of n nuts and a set B of n bolts, such that each nut in A has a unique matching bolt in B.
Unfortunately, the nuts in A all look the same, and the bolts in B all look the same as well. The only kind of a comparison that Bob can make is to take a nut-bolt pair (a,b) such that a is in B, and test it to see if the threads of a are larger, smaller, or a perfect match with the threads of b. Describe and analyze an efficient algorithm for Bob to match up all of his nuts and bolts.