Abstract

Two algorithms are presented for binding the values that occur more than n ÷ k times in an array b0:n – 1. The second one requires time proportional to n ∗ log(k) and extra space proportional to k. A theorem suggests that this algorithm is optimal among algorithms that are based on comparing array elements. Thus, finding the element that occurs more than n ÷ 2 times requires linear time, while determining whether there is a duplicate – the case k = n – requires time proportional to n ∗ log n. The algorithms may be interesting from a standpoint of programming methodology; each was developed as an extension of the algorithm for the simple case k = 2.

Links and resources

Tags

community

  • @dblp
  • @ytyoun
@ytyoun's tags highlighted