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.