Home | | Programming and Data Structure II | Accounting Method

Chapter: Programming and Data structures : Advanced Non-Linear Data Structures

Accounting Method

Assign differing charges to different operations.





–   Assign differing charges to different operations.


–   The amount of the charge is called amortized cost.


–   Amortized cost is more or less than actual cost.


– When amortized cost > actual cost, the difference is saved in specific objects as credits.


–   The credits can be used by later operations whose amortized cost < actual cost.


         As a comparison, in aggregate analysis, all operations have same amortized costs.


•   Conditions:


– Suppose actual cost is ci for the ith operation in the sequence, and amortized cost is ci',


–   åi=1n ci' ³åi=1n ci should hold.


         Since we want to show the average cost per operation is small using amortized cost, we need the total amortized cost is an upper bound of total actual cost.


         Holds for all sequences of operations.


–   Total credits is åi=1n ci' - åi=1n ci , which should be nonnegative,


         Moreover, åi=1t ci' - åi=1t ci  ≥0 for any t>0.



Accounting Method: Stack Operations


         Actual costs:


–   PUSH :1, POP :1, MULTIPOP: min(s,k).


         Let assign the following amortized costs:


–   PUSH:2, POP: 0, MULTIPOP: 0.


         Similar to a stack of plates in a cafeteria.


–   Suppose $1 represents a unit cost.


– When pushing a plate, use one dollar to pay the actual cost of the push and leave one dollar on the plate as credit.


– Whenever POPing a plate, the one dollar on the plate is used to pay the actual cost of the POP. (Same for MULTIPOP).


–   By charging PUSH a little more, do not charge POP or MULTIPOP.



         The total amortized cost for n PUSH, POP, MULTIPOP is O(n), thus O(1) for average amortized cost for each operation.


         Conditions hold: total amortized cost ≥total actual cost, and amount of credits never becomes negative.



Accounting method: binary counter


         Let $1 represent each unit of cost (i.e., the flip of one bit).


         Charge an amortized cost of $2 to set a bit to 1.


         Whenever a bit is set, use $1 to pay the actual cost, and store another $1 on the bit as




         When a bit is reset, the stored $1 pays the cost.


         At any point, a 1 in the counter stores $1, the number of 1‟s is never negative, and so is the total credit.


         At most one bit is set in each operation, so the amortized cost of an operation is at most $2.


         Thus, total amortized cost of n operations is O(n), and average is O(1).



Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail
Programming and Data structures : Advanced Non-Linear Data Structures : Accounting Method |

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

Copyright © 2018-2024 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.