Pythonの組み込み型の操作の時間計算量を一覧で解説
Time complexity of operations on Python's built-in types
Python公式ドキュメントが、list、tuple、dict、set、str、bytes、bytearray、memoryview、rangeといった主要な組み込み型の各操作の時間計算量をBig O記法でまとめています。appendやget itemがO(1)である一方、insertやdeleteは位置によってO(n)になること、dictやsetの操作は平均O(1)だが最悪ケースではO(n)になることなど、実用的なパフォーマンス特性が一目でわかります。CPythonの実装に基づく情報で、他の実装では異なる可能性がある点も注記されています。
リストの最大のコストは、現在の割り当てサイズを超えて拡張するとき（すべてを移動する必要があるため）、または先頭付近で挿入や削除を行うとき（それ以降のすべてを移動する必要があるため）に発生します。