n this problem we consider two stacks A and B manipulated using the

following operations $($n denotes the size of A and m the size of B$)$:

$$ P ushA$($x$)$: Push element x on stack A$.$

$$ P ushB$($x$)$: Push element x on stack B$.$

$$ M ultiP opA$($k$)$: Pop min$($k$,$ n$)$ elements from A$.$

$$ M ultiP opB$($k$)$: Pop min$($k$,$ m$)$ elements from B$.$

$$ T ransf er$($k$)$: Repeatedly pop an element from A and push it on B$,$ until either k elements have been

moved or A is empty.

Assume that A and B are implemented using doubly$-$linked lists such the P ushA and P ushB, as well as a

single pop from A or B$,$ can be performed in O$(1)$ time worst$-$case.

$1$

$($a$)[10$ points$]$ What is the worst$-$case running time of the operations M ultiP opA, M ultiP opB, and T ransf er$?$

$($b$)[15$ points$]$ Define a potential function $($n$,$ m$)$ and use it to prove that the operations have amortized

running time O$(1).$ Make sure to show your work.