Number of comparisons in Nuts and bolts problem
  • sorting
  • quicksort
  • matching
  • randomizedquicksort
  • noOfComparisons
  •   
  • Posted: 4 years ago
  • Updated: 3 years ago
  • Edit
  • answers (1)
  • views (3794)

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?


Posted Answers




Begin
i = 1, j = 1;
while(i < = n & & j < = n & & (i+j) < 2n - 1)
do
if a(i) < b(j)
j++;
if a(i) > b(j)
i++;
if a(i) == b(j)
if i >= j
(a,b) = (a(i), b(j));
i++;
else
(a,b) = (a(i), b(j));
j++;
End if
End if
End while
if (i > n) or (j > n)
return (a,b);
else
return (a(n),b(n));
End


\( (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.

You need to Sign In to post your solution.