Skip to main content
Definition Website Computer and Technology

Amortized Analysis

Subject: Computer and Technology noun /ˈæm.ər.taɪzd əˈnæl.ə.sɪs/ 1 definition

  1. Definition (noun)

    Entry #57 · Updated

    Amortized Analysis is an algorithmic complexity technique that bounds the average time or resource cost per operation across a worst-case sequence of operations. Instead of analyzing each operation in isolation—which can overstate total runtime when costly operations occur infrequently—it evaluates the cumulative cost of the entire sequence to show that cheap operations offset occasional expensive ones. Unlike average-case analysis, amortized analysis relies on no probabilistic assumptions about input distributions and instead establishes a deterministic upper bound for any valid operation sequence.

    Common Forms

    • Aggregate Analysis: Computes an upper bound T(n) on the total cost of any sequence of n operations and divides by n, assigning the uniform amortized cost T(n) / n to every operation regardless of type.

    • Accounting Method (Banker's Method): Assigns distinct amortized charges to different operation types, banking surplus credit from cheap operations on elements in the data structure to pay for later costly operations while keeping total stored credit non-negative.

    • Potential Method (Physicist's Method): Maps the overall state of a data structure to a scalar potential function that never drops below its initial value, defining each operation's amortized cost as its actual cost plus the resulting net change in potential.

    Example

    When appending 1,024 elements to a dynamic array (such as a C++ std::vector or Java ArrayList) that starts at capacity 1 and doubles whenever full, reallocations occur only at capacities 1, 2, 4, ..., and 512, totaling 1,023 element copies alongside 1,024 direct writes. Dividing those 2,047 total writes across all 1,024 appends gives fewer than 2 writes per insertion, proving O(1) amortized append time even though a single resize takes O(n) work.