Accounting method


Accounting method

In computational complexity theory, the accounting method is a method of amortized analysis based on accounting. The accounting method often gives a more intuitive account of the amortized cost of an operation than either aggregate analysis or the potential method. Note, however, that this does not guarantee such analysis will be immediately obvious; often, choosing the correct parameters for the accounting method requires as much knowledge of the problem and the complexity bounds one is attempting to prove as the other two methods.

The accounting method is most naturally suited for proving a O(1) bound on time. The method as explained here is for proving such a bound.

The method

Preliminarily, we choose a set of elementary operations which will be used in the algorithm, and arbitrarily set their cost to 1. The fact that the costs of these operations may in reality differ presents no difficulty in principle. What is important, is that each elementary operation has a constant cost.

Each aggregate operation is assigned a "payment". The payment is intended to cover the cost of elementary operations needed to complete this particular operation, with some of the payment left over, placed in a pool to be used later.

The difficulty with problems that require amortized analysis is that, in general, some of the operations will require greater than constant cost. This means that no constant payment will be enough to cover the worst case cost of an operation, in and of itself. With proper selection of payment, however, this is no longer a difficulty; the expensive operations will only occur when there is sufficient payment in the pool to cover their costs.

Examples

A few examples will help to illustrate the use of the accounting method.

Table expansion

It is often necessary to create a table before it is known how much space is needed. One possible strategy is to double the size of the table when it is full. Here we will use the accounting method to show that the amortized cost of an insertion operation in such a table is O(1).

Before looking at the procedure in detail, we need some definitions. Let T be a table, E an element to insert, num(T) the number of elements in T, and size(T) the allocated size of T. We assume the existence of operations create_table(n), which creates an empty table of size n, for now assumed to be free, and elementary_insert(T,E), which inserts element E into a table T that already has space allocated, with a cost of 1.

The following pseudocode illustrates the table insertion procedure: function table_insert(T,E) if num(T) = size(T) U := create_table(2 × size(T)) for each F in T elementary_insert(U,F) T := U elementary_insert(T,E)

Without amortized analysis, the best bound we can show for n insert operations is O(n2) — this is due to the loop at line 4 that performs num(T) elementary insertions.

For analysis using the accounting method, we assign a payment of 3 to each table insertion. Although the reason for this is not clear now, it will become clear during the course of the analysis.

Assume that initially the table is empty with size(T) = m. The first m insertions therefore do not require reallocation and only have cost 1 (for the elementary insert). Therefore, when num(T) = m, the pool has (3 - 1)×m = 2m.

Inserting element m + 1 requires reallocation of the table. Creating the new table on line 3 is free (for now). The loop on line 4 requires m elementary insertions, for a cost of m. Including the insertion on the last line, the total cost for this operation is m + 1. After this operation, the pool therefore has 2m + 3 - (m + 1) = m + 2.

Next, we add another m - 1 elements to the table. At this point the pool has m + 2 + 2×(m - 1) = 3m. Inserting element 2m + 1 can be seen to have total cost 2m + 1. After this operation, the pool has 3m + 3 - (2m + 1) = m + 2. Note that this is the same amount as after inserting element m + 1. In fact, we can show that this will be the case for any number of reallocations.

It can now be made clear why the payment for an insertion is 3. 1 goes to inserting the element the first time it is added to the table, 1 goes to moving it the next time the table is expanded, and 1 goes to moving one of the elements that was already in the table the next time the table is expanded.

We initially assumed that creating a table was free. In reality, creating a table of size n may be as expensive as O(n). Let us say that the cost of creating a table of size n is n. Does this new cost present a difficulty? Not really; it turns out we use the same method to show the amortized O(1) bounds. All we have to do is change the payment.

When a new table is created, there is an old table with m entries. The new table will be of size 2m. As long as the entries currently in the table have added enough to the pool to pay for creating the new table, we will be all right.

We cannot expect the first frac{m}{2} entries to help pay for the new table. Those entries already paid for the current table. We must then rely on the last frac{m}{2} entries to pay the cost 2m. This means we must add frac{2m}{m/2} = 4 to the payment for each entry, for a total payment of 3 + 4 = 7.

References

* Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. "Introduction to Algorithms", Second Edition. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Section 17.2: The accounting method, pp.410–412.


Wikimedia Foundation. 2010.

Look at other dictionaries:

  • accounting method — n. The method used by a business to calculate its income and expenditures for tax purposes. See also accrual method, cash method The Essential Law Dictionary. Sphinx Publishing, An imprint of Sourcebooks, Inc. Amy Hackney Blackwell. 2008 …   Law dictionary

  • Accounting Method — The method by which income and expenses are reported for taxation purposes. The Internal Revenue Service requires taxpayers to choose an accounting method that accurately reflects their income and to be consistent in their choice of accounting… …   Investment dictionary

  • change in accounting method — A change in the taxpayers method of accounting is an overall change in the plan of accounting, e.g. a change from the cash to the accrual method, or a change in the method of valuing inventories. Such change normally requires prior approval from… …   Black's law dictionary

  • accounting — An act or a system of making up or settling accounts, consisting of a statement of account with debits and credits arising from relationship of parties. State ex rel. King v. Harvey, Miss., 214 So.2d 817, 819. Rendition of an account, either… …   Black's law dictionary

  • accounting system — noun a bookkeeper s chronological list of related debits and credits of a business; forms part of a ledger of accounts • Syn: ↑accounting, ↑method of accounting • Derivationally related forms: ↑account (for: ↑accounting) …   Useful english dictionary

  • Accounting Rate of Return - ARR — ARR provides a quick estimate of a project s worth over its useful life. ARR is derived by finding profits before taxes and interest. ARR is an accounting method used for purposes of comparison. The major drawbacks of ARR are that it uses profit… …   Investment dictionary

  • method — meth‧od [ˈmeθəd] noun [countable] a planned way of doing something, especially one that a lot of people use: method of • It is best to consider all methods of figuring your annual income tax before deciding on any one option. method for • A buy… …   Financial and business terms

  • accounting — ac‧coun‧ting [əˈkaʊntɪŋ] noun [uncountable] 1. ACCOUNTING JOBS the usual word for the profession of accountancy in the US 2. ACCOUNTING the work of keeping a company s financial records, recording its income and expenses, and its business deals:… …   Financial and business terms

  • Accounting for leases in the United States — is regulated by the Financial Accounting Standards Board (FASB).Accounting for leases by the lesseeA lease is defined as a contractual agreement between a lessor and lessee that gives the lessee the right to use specific property, either owned by …   Wikipedia

  • accounting — /euh kown ting/, n. 1. the theory and system of setting up, maintaining, and auditing the books of a firm; art of analyzing the financial position and operating results of a business house from a study of its sales, purchases, overhead, etc.… …   Universalium


Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”

We are using cookies for the best presentation of our site. Continuing to use this site, you agree with this.