You are given n nuts and n bolts, such that one and only one nut fits each bolt.

Question

You are given n nuts and n bolts, such that one and only one nut fits each bolt. Your only means of comparing these nuts and bolts is with a function TEST(x, y), where x is a nut and y is a bolt. The function returns +1 if the nut is too big, 0 if the nut fits, and -1 if the nut is too small.

Design and analyze an algorithm for sorting the nuts and bolts from smallest to largets using the TEST
function, such that the worst case performance of the algorithm has asymptotic complexity O(n2).

Analyze the average case performance of your algorithm above.

Explanation / Answer

Choose a pivot bolt, and test it against every nut. Then test the matching

pivot nut against every other bolt. After these 2n?1 tests, we have one matched pair, and the remaining

nuts and bolts are partitioned into two subsets: those smaller than the pivot pair and those larger than

the pivot pair. Finally, recursively match up the two subsets. The worst-case number of tests made by

this algorithm is given by the recurrence

T(n) = 2n ? 1 + max 1?k?n{T(k ? 1) + T(n ? k)} = 2n ? 1 + T(n ? 1)

Along with the trivial base case T(0) = 0, this recurrence solves to

T(n) = Xn

i=1

(2n ? 1) = n

2

.

SInce this recursive algorithm looks almost exactly like quicksort, and everybody

Related Questions

Navigate

• Browse (All)
• Browse Y
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.