Вычисления режим (наиболее частый элемент) набора за линейное время?

В книге Скиены "The Algorithm Design Manual" вычисление режима (наиболее частый элемент) набора, говорят, что он имеет нижнюю границу Ω ( n log n ) (это меня озадачивает), но также (правильно я предполагаю), что не существует более быстрого алгоритма наихудшего случая для расчета режима. Я' m озадачен только тем, что нижняя граница равна Ω ( n log n ).

См. Страницу книги в Google Книгах

Но, конечно же, в некоторых случаях это может быть вычислено за линейное время (в лучшем случае), например, с помощью кода Java, как показано ниже (находит наиболее часто встречающийся символ в строке ), "хитрость" заключается в подсчете вхождений с помощью хеш-таблицы. Это кажется очевидным.

Итак, что мне не хватает в моем понимании проблемы?

РЕДАКТИРОВАТЬ: (Тайна раскрыта) Как указывает StriplingWarrior, нижняя граница сохраняется, если используются только сравнения, то есть без индексации памяти, см. Также: http://en.wikipedia.org/wiki/Element_distinctness_problem

// Linear time
char computeMode(String input) {
  // initialize currentMode to first char
  char[] chars = input.toCharArray();
  char currentMode = chars[0];
  int currentModeCount = 0;
  HashMap counts = new HashMap();
  for(char character : chars) {
    int count = putget(counts, character); // occurences so far
    // test whether character should be the new currentMode
    if(count > currentModeCount) {
      currentMode = character;
      currentModeCount = count; // also save the count
    }
  }
  return currentMode;
}

// Constant time
int putget(HashMap map, char character) {
  if(!map.containsKey(character)) {
    // if character not seen before, initialize to zero
    map.put(character, 0);
  }
 // increment
  int newValue = map.get(character) + 1;
  map.put(character, newValue);
  return newValue;
}