Matching nuts and bolts optimally

摘要: The nuts and bolts problem is the following : Given a collection of n distinct sizes such that for each nut there exactly one matching bolt, find its corresponding bolt subject to restriction we can only compare bolts. That neither nuts, nor This humble on comparisons appears make this quite difficult solve. In paper, illustrate existence an algorithm solving makes O(n lg n) nutand-bolt comparisons. We show by showing certain expander-based comparator networks. Our asymptotically optimal in terms number nut-and-bolt it does. Another view result decision tree with depth solves problem.