Eduado , só seria O(n) se você considerar que o hashing é aberto e implementado por listas lineares. Caso contrário, o hashing fechado, por exemplo, seria O(1). Como a questão menciona "quando o volume de dados armazenados cresce muito além do espaço inicialmente alocado, resulta em queda de desempenho nas operações de recuperação de dados" sugere-se que está trabalhando com um hashing aberto. Caso fosse implementado, por exemplo, o hashing dinâmico ou extensível não seria o(n), mas o(logn). Em todos os caso o(1) para encontrar a chave acrescido do (maior) tempo de percorrer uma lista, uma árvore, ou qualquer outra estrutura de dado associada ao hashing aberto. Como a complexidade assintótica considera sempre o maior tempo, neste caso, o hashing teria complexidade linear, logaritimica, etc como afirmou o colega abaixo.