CODEWITHSUNDEEP
algorithmsorting
Ashot
Ashot

Reputation: 10959

Worst case NlogN algorithm for Nuts and bolts matching

Find the unique mapping between elements of two same size arrays

This is quite known interview question and it is easy to find algorithm (using the idea of quicksort) that has O(NlogN) for average case and O(N^2) for worst case complexity. Also using the same techniques as for sorting problem we can show that any algorithm should do at least NlogN comparisons.

So the question I cant get answered, is there worst case O(NlogN) algorithm for this problem? Maybe it should be similar to merge sort.

Upvotes: 2

Views: 1133

Answers (1)

David Eisenstat
David Eisenstat

Reputation: 65458

Yes, as of 1995 there are worst-case O(n log n)-time algorithms known for this problem, but they appear to be quite complicated. Here are two citations from Jeff Erickson's algorithm notes:

  1. János Komlós, Yuan Ma, and Endre Szemerédi, Sorting nuts and bolts in O(n log n) time, SIAM J. Discrete Math 11(3):347–372, 1998.

  2. Phillip G. Bradford, Matching nuts and bolts optimally, Technical Report MPI-I-95-1-025, Max-Planck-Institut für Informatik, September 1995.

As Jeff remarks, "Both the algorithms and their analysis are incredibly technical and the constant hidden in the O(·) notation is quite large." He notes also that Bradford’s algorithm, which appeared second, is slightly simpler.

Upvotes: 4

Related Questions