Right now I'm learning about accountant amortization. There is an example that is in many textbooks and websites where they teach accountant amortization with the multi pop method of a stack. The literal cost of the stacks operations where ''' Push: 1 Pop: 1 Multipop: min(stack.size, k) ''' I understand these operations costs, but then the example always shifts to assigning amortized costs to those functions which are always ''' Push: 2 Pop: 0 Multipop: 0 ''' Why when assigning costs is push 2? Why is pop and multi pop 0? Wouldn't multi pop have a greater value than push?
Thanks for the help.
1 Answer
The sneaky thing about amortization is that real costs no longer exactly correspond to amortized costs. There's no general method for determining how operations are amortized other than you can't go bankrupt, so you could make the amortized cost of multi-pop be 5 if you wanted.
In this example, you can imagine that whenever we push an element (cost 1), we also purchase a voucher good for popping that element (cost 1, so 1 + 1 = amortized cost 2 since we did a unit of work and prepaid for another). Then we pay for the pops using vouchers only, so both pop and multi-pop are free.
