# Prove with potential method that dynamic table with $q > 1$ expansion runs in amortized constant time

Suppose I have a dynamic table supporting $$Insert$$ procedure, which sets an input value after the tail of the dynamic table. If the underlying table is already full, we multiply its size by $$q > 1$$. (I have proof that that arrangement leads to amortized constant time for $$Insert$$: see this post.)

My best attempt so far is: $$\Phi_i = \alpha n_i + \beta N_i$$, where $$n_i$$ is the number of elements in the dynamic table after the $$i$$th operation, and $$N_i$$ is the total capacity of the underlying array after the $$i$$th operation.

(1) If there is more room for a new value, $$n_i = n_{i - 1} + 1$$, and $$N_i = N_{i - 1}$$: \begin{aligned} \hat{c_i} &= c_i + \Phi_i - \Phi_{i - 1} \\ &= 1 + (\alpha n_i + \beta N_i) - (\alpha n_{i - 1} + \beta N_{i - 1}) \\ &= 1 + (\alpha n_{i - 1} + \alpha + \beta N_{i - 1}) - (\alpha n_{i - 1} + \beta N_{i - 1}) \\ &= 1 + \alpha \\ &= \Theta(1). \end{aligned}

(2) However, if there is no more room for the new value, we need to make the underlying array larger; in our case, we multiply its capacity by a constant $$q > 1$$:

Now, we have: $$n_i = n_{i - 1} + 1$$ and $$N_i = qN_{i - 1}$$: \begin{aligned} \hat{c}_i &= c_i + \Phi_i - \Phi_{i - 1} \\ &= 1 + (\alpha n_i + \beta N_i) - (\alpha n_{i - 1} + \beta N_{i - 1}) \\ &= 1 + (\alpha n_{i - 1} + \alpha + \beta qN_{i - 1}) - (\alpha n_{i - 1} + \beta N_{i - 1}) \\ &= 1 + \alpha + (q - 1) \beta N_{i - 1}. \end{aligned} ... and at this point, I am stuck.

I don't understand why you used $$1$$ as the non-amortized cost of a resizing.
Define $$\Phi_i$$ as $$\frac{q^2}{q-1}$$ times the number of elements inserted in the table since the last resizing. In formulas let $$\Phi_i = \frac{q^2}{q-1} \cdot ( i - \frac{N_i}{q} ) = \frac{q^2}{q-1} i - \frac{q}{q-1} N_i$$.
If the $$i$$-th element is inserted and no resizing happens then the worst-case cost of the operation is $$1$$ and $$N_i = N_{i-1}$$. \begin{align*} 1 + \Phi_i - \Phi_{i-1} &= 1 + \left(\frac{q^2}{q-1} i - \frac{q}{q-1} N_{i-1} \right) - \left( \frac{q^2}{q-1} (i-1) - \frac{q}{q-1} N_{i-1} \right) \\ &= 1+ \frac{q^2}{q-1}. \end{align*}
If the $$i$$-th element is inserted an a resizing happens then $$N_i = q N_{i-1}$$ and the worst-case cost of the operation is $$1 + N_i = 1 + q N_{i-1}$$. \begin{align*} 1 + q N_{i-1} + \Phi_i - \Phi_{i-1} &= 1 + q N_{i-1} + \left(\frac{q^2}{q-1} i - \frac{q^2}{q-1} N_{i-1} \right) - \left( \frac{q^2}{q-1}(i-1) - \frac{q}{q-1} N_{i-1} \right)\\ &= 1 + q N_{i-1} + \frac{q^2}{q-1} - (\frac{q^2}{q-1} - \frac{q}{q-1}) N_{i-1} \\ &= 1 + q N_{i-1} + \frac{q^2}{q-1} - q N_{i-1} \\ &= 1+ \frac{q^2}{q-1}. \end{align*}