Złożoność obliczeniowa tablicy mieszającej

W ramach projektu na uczelnię mam stworzyć tablicę mieszającą wykorzystującą algorytm md5. Z implementacją poradziłem sobie bez żadnych problemów, jednak muszę jeszcze przedstawić złożoność obliczeniową takiego algorytmu. Implenentacja jest na tyle prosta że nie wiem co tutaj obliczać :)

function dodaj($ciag){
  if(isset($this->hash_table[md5($ciag)][0])){
   $c = count($this->hash_table[md5($ciag)]);
   $this->hash_table[md5($ciag)][$c] = $ciag;
   return true;
  }else{
   $this->hash_table[md5($ciag)][0] = $ciag;
   return false;
  }
 }

Wiem że złożoność obliczeniowa jest funkcją ilości danych wejściowych i ilości wykonanych instrukcji. Jednak w takim prostym algorytmie w praktyce jedyną operacją jest sprawdzenie warunku zajętości danego indeksu i przypisanie w odpowiednie miejsca danych. Jak poradzić sobie ze złożonością obliczeniową?

wiesz że funkcja może być stała, np. f(n) = c? złożoność to O(1)

W tym przypadku tak będzie. Ale tak naprawdę nie bardzo to zobrazuje złożoność takiego algorytmu. A może zmienić warunek isset na pętle for przeszukującą tablicę indeks po indeksie?

broń Boże! niby dlaczego nie obrazuje to złożoności algorytmu? cała idea tablicy mieszającej jest taka, aby dostęp do każdego elementu był O(1). Jak chcesz mieć O(n), a tak będzie gdy zrobisz pętle, to równie dobrze możesz zrobić listę.

a tak w ogóle, to zastanawia mnie jedno. md5 genereruje 128-bit skrót. oznacza to, że musiał byś zarezerwować tablicę o rozmiarze 2^128... największe superkomputery nie mają tylko pamięci... zapewne jakoś obcinasz ten skrót?

md5 generuje skrót długości 32 znaków.

Teraz już mi dobrze nakreśliłeś problematykę :) Wielkie dzięki :)

Implementacja tego w PHP jest dość zabawna, albowiem bebechy pod spodem korzystają właśnie z tablic mieszających...
Stąd m. in. ten problem: http://niebezpiecznik.pl/post/0day-atak-dos-na-php-java-ruby-python/