Coste

Cuenta los desplazamientos

El costo de una operación se mide contando el trabajo que crece con la cantidad de valores. En el array, ese trabajo son los desplazamientos: cada valor que hay que mover un lugar.

Con n valores:

• leer(i) y escribir(i, x): 0 desplazamientos, en cualquier caso.
• insertar(i, x): n − i desplazamientos. Peor caso, i = 0: n.
• borrar(i): n − i − 1 desplazamientos.

Se escribe O(1) para «no crece con n» y O(n) para «crece en proporción a n». Siempre con su condición: aquí, el peor caso.