Construct · 1 fields · 1 citations

amortization: a standalone construct

One name. One construct. A landmark on the map.

● anchor · a standalone construct Nearest construct by meaning·not indexed
amortization1 CONSTRUCTAmortized analysisTARJAN · 1985

A single standalone construct; nearby constructs are located against it in the Collider. Tap a field for its definition, unit, and measures.

Computer science

Averaging an operation's cost over a long run

In the analysis of algorithms, amortized complexity is the average cost of an operation taken over a worst-case sequence of operations, so that an occasional expensive step is paid for by the many cheap steps around it and the per-operation bound stays low even when no single operation is cheap. Tarjan's 1985 Amortized computational complexity formalised the accounting and potential methods that charge each operation a smooth amount against a running credit. The referent is a time bound averaged over a run rather than a single call, and it is the same spread-the-cost construct as a loan's amortization, transposed from money and periods to work and operations.[1]

Unit
The average cost per operation over a worst-case sequence of operations
Recovery means
Not applicable
Measured by
Derived by the aggregate, accounting (banker's), or potential method, bounding total work across a sequence

Next

Run it through the Collider, or take the citations with you.

See how amortization sits against neighbouring constructs in the Collider, or export every reference on this page in one click.

Open in ColliderExport BibTeXReport this entry

Nearby constructs

depreciation3 fields · 3 citationsjingle · one word, three constructsallocation3 fields · 4 citationsjingle · one word, three constructsasset2 fields · 2 citationsjingle · one word, two constructs

References

  1. Tarjan, R. E. (1985). Amortized computational complexity. SIAM Journal on Algebraic Discrete Methods, 6(2), 306–318. https://doi.org/10.1137/0606031

Cited on this page?

Confirm your construct, or correct us.

If your work is cited behind one of these entries, you know better than we do whether we captured the meaning right. Confirm it, suggest an edit, or dispute it, and your name goes on the entry as an author who has checked it, linked to your ORCID.

Claim your construct