Question:
You are given a collection of nuts of different size and corresponding bolts. You can choose any nut & any bolt together, from which you can determine whether the nut is larger than bolt, smaller than bolt or matches the bolt exactly. However there is no way to compare two nuts together or two bolts together. Suggest an algorithm to match each bolt to its matching nut.

Compute time complexity of your algorithm.

Answer:
Since we can’t compare a nut with other nuts and a bolt with other bolts, we can’t sort them. So current best possibility seems to pick nuts one-by-one and find matching bolts for them. In this manner, we will match all the pairs in O(n^2) time complexity.

But though we can’t compare a nut with other nuts and so for bolts, we can compare a nut with bolts and vice-versa. Also keep in mind that if a Nut(N) is smaller than a Bolt(B) than N is fit only for bolts smaller than B. Similarly if a Bolt(B’) is smaller than a Nut(N’) than N is fit only for bolts smaller than B’. So we can go like following in solving this problem.
  • Take a nut from the nuts pile
  • Divide bolts around it in 2 parts, which are smaller and larger than this.
  • Find a matching bolt to this nut.
  • Divide nuts in 2 parts, which are smaller and larger than matching bolt.
Now we have 2 subsets of Nuts and Bolts. If we pick a nut from small size nuts pile, we will get a corresponding bolt in smaller size bolts pile and similarly for large size piles. At every step, we will be able to divide these piles in 2 halves and reduce complexity by a factor of 2 in average case. In this case time complexity will be O(nlogn).
In worst case we might have choose the smallest/largest nut/bolt as reference and our one pile will have zero nut/bolt and another pile will have all the remaining. In this case time complexity will be O(n^2).

Algorithm:
Take a nut; partition the bolts with respect to this nut. We will find the matching bolt for this nut. Now take the bolt; partition the nuts.

In this manner, we have divided the Original problems into 2 sub-problems.

T(n) = T( i ) + T(n-i ) + O(n)

Where we have chosen the ith largest nut from a particular pile.

Average time complexity = O(nlogn).
Worst time complexity = O(n^2).

Note: If more than one pair of nuts and bolts, we can divide them in 3 parts rather than 2.


Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.