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

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

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

Пример:

my_dict = {'a': 1, 'b': 2, 'c': 3}
value = my_dict['b']  # O(1) в среднем