Изменяется ли в словаре синтетическая сложноть операции

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

Пример:

d = {}
d['a'] = 1  # O(1) в среднем
value = d.get('a')  # O(1) в среднем
del d['a']  # O(1) в среднем