Parametrizando la solución

Consideremos que, o bien para ahorrar espacio o bien para mejorar el tiempo, decidimos que el arreglo no se duplicará necesariamente, sino que expandirá su tamaño a $\alpha n$ para alguna constante $\alpha>1$, de modo que a lo sumo usaremos $\alpha n$ celdas de memoria al haber leído $n$ elementos. Nos preguntamos cuál es el costo amortizado.

--> imagen

La forma más fácil de analizar el costo de inserción con este parámetro es modificar la función potencial, que seguirá siendo de la forma $\phi=an-bs$ para constantes adecuadas $a$ y $b$. Para la inserción elemental tenemos entonces $c_i=1$ y $\Delta\phi_i=a$, dando un costo amortizado de $\hat{c_i} = 1+a$. Para la expansión de tamaño $s=n$ a tamaño $s = \alpha n$ tenemos $c_i = n$ y $\Delta\phi_i = -b(\alpha-1)n$, lo cual nos da $\hat{c_i} = (1-b(\alpha-1))n$. Para que esto sea independiente de $n$ (es decir, cero como antes) debemos tener $b = \frac{1}{\alpha-1}$.

Por otro lado, para que $\phi_n \ge \phi_0$ podemos pedir que $an-bs \ge 0$ (si bien basta $an-bs \ge -b$). Como $s \le \alpha n$, basta que $a - b\alpha \ge 0$, lo cual significa que podemos elegir $a = \frac{\alpha}{\alpha-1}$. El costo amortizado, dominado por el de la inserción elemental, es entonces $1+\frac{\alpha}{\alpha-1} = \frac{2\alpha-1}{\alpha-1}$. Nuestro primer análisis correspondía entonces al caso particular $\alpha=2$, mientras que ahora podemos ahorrar espacio (aumentando el costo por operación) o reducir el costo por operación (aumentando el espacio). En todo caso, el costo por operación sigue siendo constante si el espacio extra es proporcional a $n$.