# Choosing potential function in amortized analysis of the dynamic array

Suppose we have a dynamic array with some initial capacity $$c_{initial}$$ (i.e., the dynamic array with zero elements will have this capacity). The $$add$$ operation is modified the following way:

New array capacity $$c^{‘} = c*scale$$, where the $$scale$$ is some constant if the number of elements in the array is $$s = scale^{k}$$ (i.e., the array is full, and the capacity must be increased $$scale$$ times).

I am trying to show that the $$add$$ operation has constant complexity using the following potential function: $$\Phi=scale*s-c+c_{initial}$$$$\Phi(0)=-c_{initial}+c_{initial}=0$$.

where $$s$$ is the array size (number of elements) and $$c$$ – array capacity (‘generalized’ version of the popular case when the array capacity doubles – $$\Phi=2*s-c$$ and initial capacity $$c_{initial}=0$$).

However, I stuck with the case when the scale factor is bigger than 2, for example, for $$scale=4$$ case (and initial size = 0) the cost of $$add$$ then the array is full is $$c_{i}^{‘} = c_i + \Phi_i – \Phi_{i-1} = (s+1)+(4*(s+1) – 4*c)-(4*s-c)=5+s-3*c=5-2*c$$, which is not a constant.

Is there some way besides the guess-and-check, ‘brute-force’ way to come up with an appropriate potential function?

Another possible modification of an $$add$$ operation is to increase the capacity on some constant, and I don’t see any pattern to the potential function in this case.