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.

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$.