Open AccessThe Complexity of Finding Replicas Using Equality Tests
Author(s) -
Gudmund Skovbjerg Frandsen,
Peter Bro Miltersen,
Sven Skyum
Publication year - 1993
Publication title -
daimi pb
Language(s) - English
Resource type - Journals
eISSN - 2245-9316
pISSN - 0105-8517
DOI - 10.7146/dpb.v22i437.6754
Subject(s) - combinatorics , mathematics , upper and lower bounds , set (abstract data type) , discrete mathematics , computer science , mathematical analysis , programming language
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.