Accounting Method

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 c_i for the ith operation in the sequence, and amortized cost is c_i',

–   Ã¥_i=1ⁿ c_i' ³å_i=1ⁿ c_i 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=1ⁿ c_i' - Ã¥_i=1ⁿ c_i , which should be nonnegative,

•         Moreover, Ã¥_i=1^t c_i' - Ã¥_i=1^t c_i  ≥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).