Exercise $5.$ Amortized analysis.

$[14$ points$]$

An ordered stack $\backslash (\backslash$mathcal$\{$S$\}\backslash )$ is a stack where the elements appear in increasing order. It supports the following operations:

$-\backslash (\backslash$operatorname$\{$pop$\}(\backslash$mathcal$\{$S$\})\backslash )$ : Delete and return the top element from the ordered stack.

$-\backslash (\backslash$operatorname$\{$push$\}(\backslash$mathcal$\{$S$\},$ x$)\backslash )$ : Insert $\backslash ($ x $\backslash )$ at top of the ordered stack and reestablish the increasing order by repeatedly removing the element immediately below $\backslash ($ x $\backslash )$ until $\backslash ($ x $\backslash )$ is the largest element on the stack.

$-$ destroy $\backslash ((\backslash$mathcal$\{$S$\})\backslash )$ : 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 $\backslash (\backslash$operatorname$\{$PUSH$\}(\backslash$mathcal$\{$S$\},2)\backslash )$ operation $($the order is reestablished by removing $7,5,$ and $3).$ The head of the stack is highlighted in gray.

$\backslash [$

$\backslash$begin$\{$array$\}\{|$l$|$l$|$l$|$l$|$l$|$l$|\}$

$\backslash$hline $7$ & $5$ & $3$ & $0$ & $-1$ & $-2\backslash \backslash$

$\backslash$hline

$\backslash$end$\{$array$\}\backslash$Rightarrow $\backslash$begin$\{$array$\}\{|$l$|$l$|$l$|$l$|\}$

$\backslash$hline $2$ & $0$ & $-1$ & $-2\backslash \backslash$

$\backslash$hline

$\backslash$end$\{$array$\}$

$\backslash ]$

$($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 $\backslash ($ n $\backslash )($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 $\backslash ($ n $\backslash )($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 $\backslash ($ O$(1)\backslash ).$