Какова алгоритмическая сложность поиска по словарю в худшем случае?

Для хеш-таблицы, такой как Python dict, поиск в худшем случае O(n), хотя в среднем ожидается O(1). Худший случай связан с коллизиями.

Если множество ключей попадает в конфликтующие позиции, поиск требует проверить много кандидатов. Обычно в оценке считают вычисление хеша и сравнение ключей константными; для длинных строк или пользовательских объектов их стоимость учитывают отдельно. Усреднённая константная сложность не является гарантией времени каждого отдельного обращения.