En una lista de Python, append(x) e insert(0, x) cuestan…
Opciones
- Ambas O(1) en el caso medio
- append: O(1) amortizado; insert(0): O(n) (Opción correcta)
- Ambas O(n) porque se copia la lista
- append: O(n); insert(0): O(1) en CPython
Respuesta
append O(1) amortizado, insert(0, x) O(n)
Por qué
Una lista de Python es un dynamic array: los elementos están contiguos en memoria.
Añadir al FINAL solo usa la siguiente posición libre: O(1) (a veces el array crece, pero de media sigue siendo O(1)).
Insertar al PRINCIPIO implica desplazar cada elemento una posición a la derecha: O(n). Usa collections.deque si necesitas inserciones rápidas al principio.
Recuerda
Final de la lista = rápido. Principio de la lista = lento.