### 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 (3965)

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: 4 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.