Amortized analysis for dynamic array - how to come up with a potential function?

Question

I learned about amortized analysis and the potential method, I also leaned an example of a binary counter which I think I understand well.

In the case of the binary counter I understand the choice of the potential function - we are paying in advance for a transition from one to zero that must be made in the future when a bit changes from zero to one so the potential function is how much I payed that I haven't used already.

I got an exercise to find a potential function for a dynamic array with only inserts. I understand why a dynamic array have an amortized time of $O(1)$ on inserts - either the array have sufficient size and there is a simple insert costs $O(1)$ or the array is of size $k$ and it is full and in that case we spread the cost of the $O(k)$ is costs to insert the element with the last $k/2$ elements of the array (the new elements), the amortized cost is somewhat of $O(k)/(k/2)=O(1)$.

However I can't come up with a potential function, I don't see a methodical way of taking this understanding and making it formal with the potential method.

I have found online a potential function $\Phi=2n-m$ where $n$ is the number of current elements in the array and $m$ is the size of the array, I do see a factor of $2$ maybe relating to the $2$ in the $k/2$ above, but I can't manage to get to the above $\Phi$ myself.

I would appreciate help in understanding how to take my argument and derive $\Phi$ from it

Answer 1

One method is guess-and-check. We might guess that the potential function has the form $\Phi = \alpha n + \beta m$ for some constants $\alpha,\beta$, then try to work out a proof, and see what properties $\alpha,\beta$ need to have, and look for (solve for) a value of $\alpha,\beta$ that makes the proof work out.

Another way is to use intuition. Intuitively, the idea is that some operations are slow; and other operations might be fast to complete but are going to make our life harder down the road (i.e., are going to make other operations take longer). We can then look for a potential function that charges extra for operations that are fast right now but will make life harder down the road, and then use the accumulated charges to pay for the slow operations. Intuition might help us identify which operations should increase the potential and which should decrease the potential, and then we can go from there to try to work out the specifics.