В документации Python появилась отдельная страница со сложностью операций над встроенными типами. Списки, словари, множества, строки и прочее — с пояснениями, почему именно такая сложность и какие есть нюансы.

Отдельно любопытно почитать примечания. Например, O(1) у добавления в список — амортизированная оценка: иногда приходится перевыделять память, и конкретная операция будет O(n). А у словарей поиск в среднем O(1), но при неудачных коллизиях может стать O(n). В общем, полезная шпаргалка, чтобы освежить в голове, сколько стоят привычные операции.

Ссылка https://docs.python.org/3.16/library/time-complexity.html