. You are given a collection of n bolts of different widths and n corresponding nuts....

 

Transcribed Image Text:

. You are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger than the bolt, smaller than the bolt, or matches the bolt exactly. However, there is no way to compare two nuts together or two bolts together. The problem is to match each bolt to each nut. Design an algorithm for this problem with O(n log n) average-case complexity (in terms of nut-bolt comparisons). Explain why your algorithm has (n log n) average-case complexity. You may use any result given in class without explicitly solving recurrence equations. . You are given a collection of n bolts of different widths and n corresponding nuts. You are allowed to try a nut and bolt together, from which you can determine whether the nut is larger than the bolt, smaller than the bolt, or matches the bolt exactly. However, there is no way to compare two nuts together or two bolts together. The problem is to match each bolt to each nut. Design an algorithm for this problem with O(n log n) average-case complexity (in terms of nut-bolt comparisons). Explain why your algorithm has (n log n) average-case complexity. You may use any result given in class without explicitly solving recurrence equations.

Answer rating: 100% (QA)

Here is an Onlogn averagecase algorithm for matching bolts and nuts with Onlogn averagecase complexity Sort the bolts and nuts This takes Onlogn time ... View the full answer