Finding Repeated Elements

Abstract

Two algorithms are presented for finding the values that occur more than $n \div k$ times in array b[O:n-1]. The second algorithm requires time $O(n \log(k))$ and extra space $O(k)$. We prove that $O(n \log(k))$ is a lower bound on the time required for any algorithm based on comparing array elements, so that the second algorithm is optimal. As special cases, determining whether a value occurs more than $n \div 2$ times requires linear time, but determining whether there are duplicates - the case $k=n$ - requires time $O(n \log(n))$. The algorithms may be interesting from a standpoint of programming methodology; each was developed as an extension of an algorithm for the simple case $k=2$.