The Complexity of Finding Replicas Using Equality Tests
Gudmund Skovbjerg Frandsen, Peter Bro Miltersen, Sven Skyum · DAIMI Report Series · 1993
We prove (for fixed k) that at least (1/k - 1)(^n_2) - O(n) equality tests and no more than (2/k)(^n_2) + O(n) equality tests are needed in the worst case to determine whether a given set of n elements contains a subset of k identical elements. The upper bound is an improvement by a factor 2 compared to known results. We give tighter bounds for k = 3.