Какая сложность у словаря

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

Пример:

d = {'a': 1, 'b': 2}
# O(1) операции:
d['c'] = 3  # вставка
val = d['a']  # поиск
del d['b']  # удаление

Для операций, требующих обхода (keys(), values(), items()), сложность O(n), так как нужно пройти все элементы.