Skip to main content
1 of 3
jcm
  • 169
  • 1
  • 3

Can you explain this improvement to this frequency distribution algorithm?

I came across the following in a text book:

Frequency distribution – Given a set of n items, which element occurs the largest number of times in the set? If the items are sorted, we can sweep from left to right and count them, since all identical items will be lumped together during sorting. To find out how often an arbitrary element k occurs, look up k using binary search in a sorted array of keys. By walking to the left of this point until the first the element is not k and then doing the same to the right, we can find this count in O(log n + c) time, where c is the number of occurrences of k. Even better, the number of instances of k can be found in O(log n) time by using binary search to look for the positions of both k − ε and k + ε (where ε is arbitrarily small) and then taking the difference of these positions.

The part I don't understand is the part I have emphasised in bold text - I can't understand how you might choose 'ε' and how you would know that the list even contains this 'ε'..

jcm
  • 169
  • 1
  • 3