<div>
Is this an assignment ? How far did you get ? What are you unsure about ?
</div>


Is this an assignment ? How far did you get ? What are you unsure about ?

<div>
The performance can be better than O(n^2), it should be O(n log n)
</div>


The performance can be better than O(n^2), it should be O(n log n)

<div>
<div class="content wysiwyg-content">
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.<br />
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.
</div>
</div>


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.

How to analyze an efficient algorithm?

An algorithm is a self-contained step-by-step set of operations to be performed. Algorithms exist that perform calculation, data processing, and automated reasoning. Starting from an initial state and initial input (perhaps empty), the instructions describe a computation that, when executed, proceeds through a finite number of well-defined successive states, eventually producing "output" and terminating at a final ending state. The transition from one state to the next is not necessarily deterministic; some algorithms, known as randomized algorithms, incorporate random input.