La complejidad temporal de las operaciones en los tipos integrados de Python
Time complexity of operations on Python's built-in types
La documentación oficial de CPython detalla, mediante notación Big O, el coste temporal de las operaciones sobre los tipos integrados: listas, tuplas, diccionarios, conjuntos, cadenas, bytes, bytearray, memoryview y range. Incluye casos promedio y peor caso, y señala que copiar una tupla o cadena es O(1) porque devuelve el mismo objeto, mientras que insertar o borrar al principio de una lista es O(n). También advierte que las operaciones de dict y set pueden degradarse a O(n) si las claves colisionan.
Los mayores costes provienen de crecer más allá del tamaño de asignación actual (porque todo debe moverse), o de insertar o eliminar cerca del principio (porque todo lo posterior debe moverse).