choosing a potential function
The potential method gives you a turn-the-crank formula once you have a potential function Phi, but it stays silent on where Phi comes from. Finding a good Phi is the real art of amortized analysis. A good potential is a number that measures how much 'pent-up future cost' the structure is currently storing — high when an expensive operation is looming, low right after one has cleaned things up.
Two guideposts make the search tractable. First, Phi must respect the boundary condition: it should never fall below its initial value (the easy way is Phi >= 0 with Phi(empty) = 0), or the telescoping sum stops being an upper bound. Second, and this is the design heuristic, pick Phi so that cheap operations raise it only a little while the expensive operation drops it by roughly its own large cost. Then expensive operations get their actual cost mostly cancelled by the fall in Phi, and everything's amortized cost comes out small. Practically, you look at what makes an operation expensive — many elements to copy, a long carry chain, a deep unbalanced path — and let Phi count exactly that pending work. For a dynamic array near full, a workable potential is Phi = 2*(number of items) - capacity, which is small just after a resize and grows as the array fills, so it is large precisely when the next costly doubling is due.
Choosing a potential is guess-and-check guided by intuition: propose a Phi, compute amortized = actual + (Phi_after - Phi_before) for each operation, and see whether they all come out small and the boundary condition holds. If some operation's amortized cost is still large, the potential is wrong and you revise it. The honest reality: there is no algorithm that hands you Phi; for hard structures like splay trees the right potential (sum of logarithms of subtree sizes) took genuine insight to discover. A wrong choice does not give a wrong answer, only a useless bound — so it is safe to experiment.
Dynamic array that doubles, with Phi = 2*size - capacity. A non-resizing append raises size by 1, so Phi rises by 2; amortized = 1 (write) + 2 = 3. When a full array of capacity c doubles, the copy costs c, but Phi drops from 2c - c = c to 2c - 2c = 0 just before refilling — the c-unit drop cancels the c-unit copy, keeping that append's amortized cost O(1) too.
Let the potential count the pending expensive work; cheap operations add a little, the expensive one releases a lot.
There is no recipe that produces Phi for you. A bad potential never yields a false bound, only a loose or useless one, so guessing is safe — but the right Phi for hard structures can require real cleverness.