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

PushA(x): Push element x on stack A.

PushB(x): Push element x on stack B.

MultiPopA(k): Pop min{k, n} elements from A.

MultiPopB(k): Pop min{k, m} elements from B.

Transfer(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 that PushA and PushB, as well as a single pop from A or B, can be performed in O(1) time worst-case.

(a) What is the worst-case running time of the operations MultiPopA, MultiPopB and Transfer?

(b) Define a potential function (n, m) and use it to prove that the operations have amortized running time O(1).

In 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): PushA(x): Push element on stack A PushB(x): Push element z on stack B. MultiPopA(k): Pop mink,n elements from A. MultiPopB(k): Pop min(k, m) elements from B. Transfer(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 that PushA and PushB, as well as a single pop from A or B, can be performed in O(1) time worst-case (a) 5 points] What is the worst-case running time of the operations MultiPopA, Multi PopB and Transfer? (b) 125 points! Define a potential function (n, m) and use it to prove that the operations have amortized running time