В Python средняя сложность получения значения из словаря (dict) — O(1), но в худшем случае может быть O(n). Это происходит из-за коллизий хэш-функции, когда несколько ключей попадают в один и тот же хэш-бакет. В таком случае поиск значения превращается в линейный поиск по списку в этом бакете. Пример: ``` d = {} # Намеренно создаем коллизии (редкий случай) for i in range(1000): d[i] = i # Если все ключи попали в один бакет, поиск O(n) value = d[999] # В худшем случае O(n) ``` Обычно Python корректирует размер хэш-таблицы, чтобы минимизировать коллизии, но теоретически худший случай возможен.