Uma busca em lista compara valores até encontrar uma correspondência. Uma consulta em dicionário usa outra estrutura de dados, e apagar o primeiro item de uma lista desloca as referências restantes. Esses detalhes importam quando uma pequena função auxiliar fica dentro de um loop executado com muita frequência.
Aqui você conta operações em vez de cronometrar um navegador. Uma contagem é reproduzível e deixa o crescimento visível. Ela também obriga você a dizer o que contou: comparações, referências deslocadas, visitas à entrada ou pares não ordenados. As consultas em tabelas hash têm custo constante em média em condições normais; isso é um modelo com premissas, não uma garantia para qualquer objeto ou padrão de colisões. Preserve os resultados ao trocar o contêiner.
Conte também a comparação bem-sucedida; uma consulta por um valor ausente percorre todos os itens. Use um contador de comparações novo para cada consulta. Percorra a lista até o primeiro valor igual. Com n itens e q consultas, o número de comparações no pior caso cresce como n vezes q.