An

ordered stack

$$

is a stack where the elements appear in increasing order. It

supports the following operations:

$$

pop

$($

$$

$)$: Delete and return the top element from the ordered stack.

$$

push

$($

$$

$,$

$$

$)$: Insert

$$

at top of the ordered stack and reestablish the increasing

order by repeatedly removing the element immediately below

$$

until

$$

is the

largest element on the stack.

$$

destroy

$($

$$

$)$: 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

push

$($

$$

$,2)$ operation $($the order is reestablished by removing $7,5,$

and $3).$ The head of the stack is highlighted in gray.

$7$

$5$

$3$

$0$

$-1$

$-2$

$$

$2$

$0$

$-1$

$-2$

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

$$

$($possibly mixed$)$ operations

pop

$,$

push

$,$ and

destroy

$.$

Propose an amortized cost for each of these operations that guarantee the credit