(Solved): Exercise 5. Amortized analysis. [14 points] An ordered stack \( \mathcal{S} \) is a stack where the ...

Exercise 5. Amortized analysis. [14 points] An ordered stack \( \mathcal{S} \) is a stack where the elements appear in increasing order. It supports the following operations: - \( \operatorname{pop}(\mathcal{S}) \) : Delete and return the top element from the ordered stack. - \( \operatorname{push}(\mathcal{S}, x) \) : Insert \( x \) at top of the ordered stack and reestablish the increasing order by repeatedly removing the element immediately below \( x \) until \( x \) is the largest element on the stack. - destroy \( (\mathcal{S}) \) : Delete all elements in the ordered stack (i.e., which results in an empty ordered stack). Example. The following shows an example of an ordered stack and the same stack after performing a \( \operatorname{PUSH}(\mathcal{S}, 2) \) operation (the order is reestablished by removing 7,5 , and 3 ). The head of the stack is highlighted in gray. \[ \begin{array}{|l|l|l|l|l|l|} \hline 7 & 5 & 3 & 0 & -1 & -2 \\ \hline \end{array} \Rightarrow \begin{array}{|l|l|l|l|} \hline 2 & 0 & -1 & -2 \\ \hline \end{array} \] (a) (2 points) What is the worst-case running time of each of the operations pop, PUSh, and destroy? No justification required. (b) (4 points) We would like to apply the accounting method to make an amortized analysis of a sequence of \( n \) (possibly mixed) operations POP, PUSh, and destroy. Propose an amortized cost for each of these operations that guarantee the credit Page 4 will never go negative while minimizing the cost. Justify your answer if the proposed amortized cost is different than 0. (c) (6 points) Now, consider any sequence of \( n \) (possibly mixed) operations POP, PUSH, and pestroy. At the beginning the ordered stack is empty. Using the amortized costs you proposed above, demonstrate that the credit (i.e., the amortized cost minus the actual cost) never goes negative. (d) (2 points) Explain why the guarantee that the credit does not go negative helps you to conclude that the amortized cost of a single operations is \( O(1) \).