Finding the Equation for Potential Method and Amortization Analysis

Question

I am trying to figure out the solution to this problem:

In this problem we consider two stacks $A$ and $B$ manipulated using the following operations ($n$ denotes the size of $A$ and $m$ the size of $B$):
  PushA($x$): Push element $x$ on stack $A$.
  PushB($x$): Push element $x$ on stack $B$.
  MultiPopA($k$): Pop $\min(k; n)$ elements from $A$.
  MultiPopB($k$): Pop $\min(k;m)$ elements from $B$.
  Transfer($k$): Repeatedly pop an element from $A$ and push it on $B$, until either $k$ elements have been moved or $A$ is empty.

I need to define a potential function $\phi(n;m)$. The solution guide comes up w/ a function of $3n+m$. How can we come up with that function?

Answer 1

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.