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 *c _{i}* for the

â€“ Ã¥_{i}_{=1}^{n}* c _{i}*'

â€¢
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}^{n}*c _{i}*' - Ã¥

â€¢
Moreover, Ã¥_{i}_{=1}^{t}*c _{i}*' - Ã¥

**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 |

**Related Topics **

Privacy Policy, Terms and Conditions, DMCA Policy and Compliant

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