The Complexity of Identifying Large Equivalence Classes

Peter G. Binderup
Gudmund Skovbjerg Frandsen
Peter Bro Miltersen
Sven Skyum

December 1998


We prove that at least tex2html_wrap_inline32 equivalence tests and no more than tex2html_wrap_inline34 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 tex2html_wrap_inline42 we prove that it is necessary and it suffices to make 2n-k-1 equivalence tests which generalizes a known result for tex2html_wrap_inline46

Available as PostScript, PDF, DVI.


Last modified: 2003-06-08 by webmaster.