Berechnung des Modus (häufigste element) eines Satzes in der linearen Zeit?

In dem Buch "the Algorithm Design Manual" von Skiena, Berechnung der Modus (häufigste element) eines Satzes, so wird gesagt, eine Ω - (n log n) untere Schranke (das verwirrt mich), aber auch (korrekt denke ich), dass kein schneller worst-case-Algorithmus existiert, der für die Berechnung des Modus. Ich bin nur verwirrt durch die untere Schranke als Ω(n log n).

Finden Sie auf der Seite des Buches auf Google Bücher

Aber sicherlich könnte dies in einigen Fällen berechnet werden, in linearer Zeit (best case), z.B. durch Java-code wie unten (findet die häufigste Zeichen in einem string), der "trick" sein, um zu zählen Ereignisse mit Hilfe einer hashtable. Dies scheint offensichtlich.

So, was bin ich in meinem Verständnis für das problem?

EDIT: (Rätsel gelöst) Als StriplingWarrior Punkte out die untere Schranke gilt, wenn nur Vergleiche werden verwendet, also keine Indizierung von Speicher, siehe auch: 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<Character, Integer> counts = new HashMap<Character, Integer>();
  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<Character, Integer> 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;
}