TY - JOUR
AU - Peter Binderup
AU - Gudmund Frandsen
AU - Peter Miltersen
AU - Sven Skyum
PY - 1998/06/04
Y2 - 2020/08/15
TI - The Complexity of Identifying Large Equivalence Classes
JF - BRICS Report Series
JA - BRICS
VL - 5
IS - 34
SE - Articles
DO - 10.7146/brics.v5i34.19440
UR - https://tidsskrift.dk/brics/article/view/19440
AB - We prove that at least (3k−4) / k(2k−3) n(n-1)/2 − O(k) equivalence tests and nomore than 2/k n(n-1)/2 + O(n)equivalence tests are needed in the worst case to identify the equivalence classes with at least k members in set of n elements. The upper bound is an improvement by a factor 2 compared to known results. For k = 3 we give tighter bounds. Finally, for k > n/2 we prove that it is necessary and it suffices to make 2n − k − 1 equivalence tests which generalizes a known result for k = [(n+1)/2] .
ER -