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).