Здесь описана сложность исполнения основных операций над словарями.
В таблице ниже приводится усреднённая сложность. Амортизированный худший случай обычно описывается O(n). Для усреднённой сложности предполагается, что хеш-функция для словарей в состоянии сделать конфликты редкими. Также предполагается, что ключи, используемые в параметрах, выбираются равномерно из множества всех существующих ключей.

На заметку
Далее n — количество элементов в контейнере; k — значение параметра, либо количество элементов в параметре.

Указанная ниже сложность справледлива и для defaultdict (вместе с доступными операциями они наследуют от словарей и их сложности). Предполагается, что конструирование нового defaultdict имеет сложность O(1) (что справледливо для часто используемых int(), list(), set()).

Обращение по индексу O(1) d[k]
Присвоение O(1) d[k] = v
len O(1) len(d)
del O(1) del d[k]
.setdefault O(1) d.setdefault(1)
.pop O(1) d.pop(k)
.popitem O(1) d.popitem()
.clear O(1) d.clear() То же: d = {} и d = dict().
Представление O(1) d.keys()
Создание O(k) dict(obj) Зависит от числа кортежей (ключ, значение).
Проход O(n) for k in d: То же для keys(), values(), items().
.copy O(n) d1 = d.copy()

На заметку
Для словарей, где ключи являются строками, используется быстрый путь. Это не оказывает влияния на алгоритмическую сложность, однако сильно влияет на постоянные факторы — то, на сколько быстро исполяется типовое приложение.

Нет обсуждений для отображения.
Если у вас есть, что сказать, можете представиться и исправить ситуацию.