• 0

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

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

  • Posted: 5 years ago
  • 0 0
  • Edit




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.