Home | | Programming and Data Structure II | Accounting Method

# Accounting Method

Assign differing charges to different operations.

ACCOUNTING METHOD:

â€˘         Idea:

â€“   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

credit.

â€˘         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 |