How will you design an efficient algorithm to find the smallest bolt and its matching nut , instead of the all matching pairs of nuts and bolts in the ( Nuts and bolts problem ). How many comparisons you made in your algorithm?
\( (a,b) \) \( \rightarrow \) \( a \) possible choices from the set of nuts and \( b \) possible choices from the set of bolts. Initially \( a=b=n \). After each comparisons, we discard at most one of the possible elements. After a comparison \( (a,b) \) can be either \( (a,b) \) or \( (a-1,b) \) or \( (a,b-1) \). The algorithm stops when we reach \( (1,1) \). \( \therefore \) In the worst case, number of comparisons is \( (2n-2) \) atleast. |