В каком случае алгоритмическая сложность получения значения словаря равна O(n)

В Python средняя сложность получения значения из словаря (dict) — O(1), но в худшем случае может быть O(n). Это происходит из-за коллизий хэш-функции, когда несколько ключей попадают в один и тот же хэш-бакет. В таком случае поиск значения превращается в линейный поиск по списку в этом бакете.

Пример:

d = {}
# Намеренно создаем коллизии (редкий случай)
for i in range(1000):
    d[i] = i
# Если все ключи попали в один бакет, поиск O(n)
value = d[999]  # В худшем случае O(n)

Обычно Python корректирует размер хэш-таблицы, чтобы минимизировать коллизии, но теоретически худший случай возможен.