Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
Consider the follow operations on a stack of size at most $k$.
Push - insert element in the stack - actual cost 1
Pop - remove top element from the stack - actual cost 1
Copy - copy whole stack (but maintain the number of elements) - actual cost is the number of elements in the stack
Prove using the potential method that each single operation (push, pop or copy) has amortized cost at most 2.
What would be a suitable potential function for this problem?
A reasonable potential function here would be $C\ell$ or $C(k-\ell)$, where $\ell$ is the number of elements on the stack.
However, I don't think that the amortized cost can be bounded. Consider $k$ push operations followed by $M$ copy operations. The total cost is $k(M+1)$. If the amortized cost of push is $a$ and of copy is $b$, then $ka + Mb \geq k(M+1)$. Dividing by $M$ and letting $M\to\infty$, we obtain $b \geq k$.
Let us consider a particular potential function in the context of amortized analysis:
$$ \hat{c_i} = c_i + \phi(D_i) - \phi(D_{i-1}) $$
Let's assume we have some stack $S$.
So let's look at push — this has an actual cost of 1, so it's potential function will look like
$$ \hat{c_i} = 1 + (|S| + 1) - |S| \rightarrow 1 + 1 \rightarrow 2 $$
Similarly, pop has an actual cost of 1, so we get
$$ \hat{c_i} = 1 + (|S| - 1) - |S| \rightarrow 1 - 1 \rightarrow 0 $$
Finally, copy has an actual cost of $|S|$ so we end up with
$$ \hat{c_i} = |S| + |S| - |S| \rightarrow |S| + 0 \rightarrow |S| $$
Prove using the potential method that each single operation (push, pop or copy) has amortized cost at most 2.
As you can see, the amortized cost for copying the entire stack will always be $|S|$ since copying does not affect the potential energy of your stack.
However, both push and pop have an amortized cost of at most 2.
