You are given a set of n nuts and another set of n bolts such that they form n distinct pairs of matching nuts and bolts, i.e., each of the bolts go into one nut only. What will the number of comparisons to maching operation conducted in an effective manner? (Note: The only allowed operation is trying to fit a bolt into a nut and thereby concluding whether they are of equal size, or find out which is greater in size)
Here, we are going to follow a quick sort algorithm.
Firstly, select a nut and partition the bolt array with bolt that perfectly fits as the pivot and the ones larger than the selected nut on right side and smaller ones on the left side.
Similarly, partition the nuts array using the perfect fit for selected nut in the first step.
Now apply the first two steps on the two partitions we got and repeat the process until we get a match for each nut and bolt.
Therefore, the number of comparisions made will be 2n log(n).
Hence the complexity O(nlog(n))