Una búsqueda en una lista compara valores hasta encontrar una coincidencia. Una consulta en un diccionario usa otra estructura de datos, y borrar el primer elemento de una lista desplaza las referencias restantes. Estos detalles importan cuando una pequeña función auxiliar está dentro de un bucle con mucha carga.
Aquí cuentas operaciones en lugar de cronometrar un navegador. Un recuento es reproducible y deja ver el crecimiento. También te obliga a decir qué has contado: comparaciones, referencias desplazadas, visitas a la entrada o pares sin orden. Las consultas en tablas hash tienen un coste constante en promedio en condiciones normales; es un modelo con supuestos, no una garantía para cualquier objeto o patrón de colisiones. Conserva los resultados mientras cambias el contenedor.
Cuenta también la comparación que acierta; una consulta que no está recorre todos los elementos. Usa un contador de comparaciones nuevo para cada consulta. Recorre la lista hasta el primer valor igual. Con n elementos y q consultas, el número de comparaciones en el peor caso crece como n por q.