1
$\begingroup$

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?

$\endgroup$
  • 1
    $\begingroup$ What have you tried? Where did you get stuck? We're happy to help you understand the concepts but just solving exercises for you is unlikely to achieve that. You might find this page helpful in improving your question. $\endgroup$ – D.W. Mar 28 '17 at 16:23
1
$\begingroup$

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$.

$\endgroup$
  • $\begingroup$ Thank you for the answer. I really the question was 'prove that each operation' and not a sequence of them. I've edited it, although I'm not sure it makes a difference to your conclusion. $\endgroup$ – joaoaccarvalho Mar 28 '17 at 15:43
  • 1
    $\begingroup$ I don't understand your comment. Amortized cost is an upper bound on the average cost of an operation in an arbitrary sequence of operations (the exact definition is a bit more complicated). If the copy operation deleted the stack, then indeed you could bound the amortized cost by some constant. As it is, there seems to be a mistake in the question. $\endgroup$ – Yuval Filmus Mar 28 '17 at 15:47
0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ In amortized analysis we are free to choose whatever potential function we want. You are using a particular one. In fact, with a constant potential the cost of push and pop would be only 1. $\endgroup$ – Yuval Filmus Mar 28 '17 at 17:13
  • $\begingroup$ @YuvalFilmus Ah you're right, thank you for pointing that out. Does this affect my conclusion? $\endgroup$ – Nick Zuber Mar 28 '17 at 19:02
  • $\begingroup$ You're analyzing a particular potential function. Perhaps a different one will lead to better conclusions? $\endgroup$ – Yuval Filmus Mar 28 '17 at 19:18

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.