Como é determinada a complexidade temporal da operação de adicionar um elemento a uma tabela hash?

A complexidade temporal da operação de adicionar um elemento a uma tabela de hash é geralmente considerada amortizada O(1). Isso significa que, em média, a adição ocorre em tempo constante, pois o elemento é colocado imediatamente na cubeta correspondente pelo hash. No entanto, no pior caso, se ocorrer uma colisão (vários elementos na mesma cubeta), ou quando for necessário expandir a tabela (rehash), a operação pode levar O(n) tempo, onde n é o número de elementos na tabela. Mas, graças a uma boa função de hash e ao controle de carga da tabela, esses casos são raros.