The Complexity of Identifying Large Equivalence Classes

Research output: Contribution to journal/Conference contribution in journal/Contribution to newspaperJournal articleResearch

  • Department of Computer Science
  • Studies Office, Faculty of Science
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].
Original languageEnglish
JournalFundamenta Informaticae
Pages (from-to)25-37
Number of pages12
Publication statusPublished - 1999

See relations at Aarhus University Citationformats

ID: 21681136