Amortized analysis is a technique for showing how to distribute the total cost of a worst case sequence of operations among all the operations in the sequence to get an average cost. So even if there are operations that are expensive, as long as there are enough cheap operations, the average cost will be cheap. In your case, a push
is cheap, assuming it takes 1 step, while a multipop
and transfer
are expensive since they require non-constant amount of steps.
When cost are distributed among operations, the cost of expensive operations decreases while the cost of cheap operations increases, compared to their actual cost. Now a potential function is a way to quantify this difference between the average cost (also called the amortized cost) and the actual cost. The potential may increase for cheap operations and may decrease for expensive operations. A potential function is correctly defined if all increase in potential are enough to shoulder all decrease.
Before you define any potential function, make sure you have an intuition as to how to distribute the cost of expensive operations to cheap operations:
A multipop
pops multiple elements previously pushed. Assuming that one pop takes a step, the cost of a multipop
can be covered if one additional step is charge to a push
for a pop in a multipop
. This additional charge to push
must increase the potential. And performing a multipop
should consume that same amount of increase.
A transfer
is like a multipop
on stack $A$ followed by a sequence of push
on stack $B$. If the cost of a push in $A$ can be additionally charged again when an item is popped from $A$ and then another when it is pushed to $B$, then the cost of transfer
can be covered. This again should increase the potential when performing a push
and decrease when a transfer
is performed.
From above the cost of a push in stack $A$ will have 3 extra charge while a push in $B$ will have 1 extra charge. Now think of a way to represent these extra charges using some properties of the data structure. An easy and hopefully intuitive way is to associate the charges with the number of elements in both stacks, since the change in the number of elements is in parallel to change in potential. That is, associate a value of 3 to each element in $A$ and associate a value of 1 for those in $B$. This should give you $3n + m$.
On a final note, there can be more than one way to define a potential function. In the above definition, the amortized cost of both multipop
and transfer
are zero, so they are essentially free of charge.