The Complexity of Identifying Large Equivalence Classes

Article type: Research Article

Authors: Skyum, Sven | Frandsen, Gudmund S. | Miltersen, Peter Bro | Binderup, Peter G.

Affiliations: BRICS, Basic Research in Computer Science, Centre of the Danish National Research Foundation, Department of Computer Science, University of Aarhus.

Note: [] Address for correspondence: BRICS, Basic Research in Computer Science, Centre of the Danish National Research Foundation, Department of Computer Science, University of Aarhus.

Abstract: We prove that at least 3k−4/k(2k−3)(n/2) – O(k)equivalence tests and no more than 2/k (n/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].

DOI: 10.3233/FI-1999-381203

Journal: Fundamenta Informaticae, vol. 38, no. 1-2, pp. 25-37, 1999