Cuando hablamos de complejidades Asintóticas generalmente tenemos en cuenta n muy grande. Ahora para el manejo de colisiones en una Tabla hash algunos de los métodos están encadenados hash & sondeo lineal. En ambos casos, pueden suceder dos cosas (que ayudarán a responder su pregunta): 1. Es posible que deba cambiar el tamaño de la tabla hash debido a que se llena 2. Pueden producirse colisiones.
En el peor de los casos, dependerá de cómo haya implementado su tabla hash, por ejemplo, en el sondeo lineal no encuentra el número, sigue moviéndose y el número que estaba buscando estaba al final. Aquí viene el peor tiempo de ejecución de O (n). Viniendo a la técnica de hash encadenada, cuando ocurre una colisión, para manejarlos digamos que hemos almacenado las claves en un árbol binario balanceado para que el peor tiempo de ejecución del caso sea O (log n).
Ahora, llegando al mejor tiempo de ejecución de casos, creo que no hay confusión, en cualquier caso sería O (1).
O (n) ocurriría en el peor de los casos y no en un caso promedio de una buena tabla hash diseñada. Si eso comienza a suceder en las tablas hash de casos promedio, no encontrará un lugar en Data Structures porque los árboles balanceados en promedio le darán O (log n) siempre y ON TOP OF THAT también conservará el orden.
Disculpe, pero lamentablemente su amigo tiene razón. Su caso sucedería en el peor de los casos.
también mira aquí para cosas más informativo es decir, el tiempo de ejecución amortizado: Time complexity of Hash table
me gustaría añadir a la respuesta Yavar: recordar, que O (1) no es una op. Podría ser una gran constante, pero eso no importa si no se deriva de una variable como n. Incluso si necesita pasar por 20 nodos para colocar un hash, sigue siendo un O (1). Por supuesto, eso funciona para la tabla hash solo si algunas condiciones son ciertas, pero para la tabla hash bien diseñada que es O (1) en promedio – Archeg