Amortized analysis

Amortized analysis bounds the total cost of a sequence of operations, yielding a guaranteed average cost per operation even when individual operations vary widely.

Aggregate method: A method that bounds the total cost of a sequence, then divides by the number of operations. It derives the amortized cost directly from a sequence-wide total.
Algorithm analysis: The study of an algorithm's resource use as a function of input size. Amortized analysis is one way to characterize algorithmic resource use.
Dynamic array: An array that can grow or shrink by allocating storage as needed. Geometric resizing gives constant amortized insertion cost despite occasional copying.
Average-case analysis: An analysis of expected or mean performance over a distribution of inputs. Its averaging depends on an input distribution, unlike amortization's sequence guarantee.
Accounting method: A method that assigns credits to operations so earlier cheap operations can pay for later expensive ones. Stored credits make the cost of rare expensive operations explicit.
Asymptotic analysis: The study of how resource use grows as input size becomes large. Amortized costs are often reported with asymptotic bounds.
Binary counter: A counter represented by binary digits, incremented by flipping bits. Across many increments, each bit flips only a bounded number of times per scale.
Online algorithm: An algorithm that processes input incrementally without knowing future input in advance. Amortized bounds often certify online performance over every operation sequence.
Potential method: A method that tracks stored work as a potential function over a data structure's states. Potential changes convert actual operation costs into amortized costs.
Data structure: A method for organizing data to support operations efficiently. Operation sequences on data structures are a central setting for amortized bounds.

Linked from 14 pages