The Complexity of Finding Replicas Using Equality Tests

Authors

  • Gudmund Skovbjerg Frandsen
  • Peter Bro Miltersen
  • Sven Skyum

DOI:

https://doi.org/10.7146/dpb.v22i437.6754

Abstract

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.

Author Biographies

Gudmund Skovbjerg Frandsen

Peter Bro Miltersen

Sven Skyum

Downloads

Published

1993-04-01

How to Cite

Frandsen, G. S., Miltersen, P. B., & Skyum, S. (1993). The Complexity of Finding Replicas Using Equality Tests. DAIMI Report Series, 22(437). https://doi.org/10.7146/dpb.v22i437.6754

Issue

No. 437 (1993): PB-437 The Complexity of Finding Replicas Using Equality Tests

Section

Articles

License

Creative Commons License

Articles published in DAIMI PB are licensed under a Creative Commons Attribution-NonCommercial-NoDerivs 3.0 Unported License.