Amortized analysis is a method for analyzing the cost of a sequence of operations in a data structure or algorithm. It is especially useful when most operations are inexpensive but occasional operations are expensive. Unlike average-case analysis, amortized analysis does not rely on a probability distribution over inputs. Instead, it proves that the total cost of any valid sequence of operations is bounded, and then distributes that total cost across the operations. A common example is appending elements to a dynamic array. Most append operations take constant time because the new element can be placed in an available position. Occasionally, the array becomes full and must allocate a larger storage area and copy its existing elements. That individual append operation can take linear time. However, if the array capacity is doubled whenever it becomes full, the expensive resizing operations occur increasingly far apart. Across a long sequence of m appends, the total number of copied elements is bounded by a geometric sum proportional to m. Therefore, the total cost is O(m), giving O(1) amortized cost per append. Three common techniques are the aggregate method, the accounting method, and the potential method. The aggregate method bounds the total sequence cost directly. The accounting method assigns credits to inexpensive operations to pay for future expensive operations. The potential method uses a mathematical potential function to track stored credit or prepaid work in the data structure. Amortized analysis is useful for understanding data structures whose occasional costly operations are balanced by many inexpensive ones.
Amortized Analysis
Amortized analysis evaluates the average cost per operation over a sequence of operations, even when individual operations have different costs.
Amortized cost per operation = Total cost of a sequence of m operations / m.
Explanation
Variables
| Symbol | Meaning | Unit |
|---|---|---|
m | Number of operations in the analyzed sequence. | Operations |
cᵢ | Actual cost of the i-th operation. | Operations or cost units |
C(m) | Total actual cost of the complete operation sequence. | Cost units |
ĉᵢ | Amortized cost assigned to the i-th operation. | Cost units |
Example or application
Suppose a dynamic array doubles its capacity whenever it becomes full. Across 8 append operations, the array may resize from capacity 1 to 2, then 4, then 8. The copying work is 1 + 2 + 4 = 7 element copies, in addition to the 8 insertions. The total work is 15 basic operations under this simplified model, so the average cost across the sequence is 15/8, a constant. As the sequence grows, the geometric sum remains proportional to the number of appends.
Key Properties
Analyzes sequences of operations rather than only one isolated operation.
Allows occasional expensive operations.
Provides a guaranteed bound over valid operation sequences.
Does not require a probability distribution over inputs.
Aggregate, accounting, and potential methods are standard techniques.
Dynamic-array append is a common example with O(1) amortized cost under capacity doubling.
Prerequisites
Understanding of arrays and dynamic arrays.
Basic operation-count analysis.
Familiarity with geometric sequences.
Understanding of worst-case and average-case analysis.
Learning Objectives
Explain the purpose of amortized analysis.
Distinguish amortized analysis from average-case analysis.
Understand why an occasional expensive operation may have constant amortized cost.
Describe the aggregate, accounting, and potential methods.
Core Concepts
Operation sequence
Actual cost
Amortized cost
Dynamic-array resizing
Aggregate method
Accounting method
Potential method
Step By Step
Identify the sequence of operations being performed.
Determine the actual cost of each operation.
Include occasional expensive operations such as resizing or rebuilding.
Calculate or bound the total cost of the complete sequence.
Divide the total bound by the number of operations to obtain the amortized bound.
State clearly whether the result applies to each operation or to the sequence as a whole.
Pseudocode
ALGORITHM DynamicArrayAppend(A, value)
IF A is full
newCapacity = 2 * currentCapacity
CREATE new storage with newCapacity
COPY existing elements into new storage
REPLACE old storage
END IF
INSERT value at the next available position
INCREASE element count
Complexity
Time
O(1) amortized per append; O(n) worst-case for an individual append that triggers resizing.
Space
O(n) storage for n elements, with additional unused capacity possible.
Explanation
Most appends require constant work. Resizing may require copying all existing elements, but geometric capacity growth makes the total copying work across m appends O(m).
Applications
Dynamic-array append operations.
Stack operations with automatic resizing.
Hash-table resizing and rebuilding.
Disjoint-set union data structures.
Operations on self-adjusting data structures.
Algorithms with occasional expensive maintenance operations.
Common Mistakes
Claiming every individual operation is constant time when some operations are expensive.
Confusing amortized analysis with probabilistic average-case analysis.
Ignoring the total cost of resizing operations.
Dividing by the wrong number of operations.
Assuming amortized bounds automatically describe every possible random input distribution.
Key Takeaways
Amortized analysis studies the total cost of a sequence of operations.
An individual operation can be expensive even when its amortized cost is small.
Dynamic-array append is O(1) amortized under geometric capacity growth.
The aggregate, accounting, and potential methods provide different ways to prove amortized bounds.
Related Topics
Constant Time Complexity
Dynamic Arrays
Worst-Case Analysis
Average-Case Analysis
Complexity Comparison and Growth Rates
Limitations
The suitability of amortized analysis depends on the exact problem requirements and the assumptions made about the input.
An implementation of amortized analysis can fail if its boundary conditions, data representation, or required invariants are handled incorrectly.
For amortized analysis, evaluate representative and unusually difficult inputs; a single small demonstration is not enough to establish reliability.
Practice Questions
| Question | Answer |
|---|---|
What is the main purpose of amortized analysis? | Amortized analysis evaluates the average cost per operation over a sequence of operations, even when individual operations have different costs. |
What should be checked before applying amortized analysis? | For amortized analysis, verify the stated inputs, assumptions, expected result, boundary cases, and time and memory constraints. |
How can an implementation of amortized analysis be validated? | Trace a representative amortized analysis case manually, test its boundary conditions, and compare the result with the specification or a trusted baseline. |
Sources and verification
Sources are shown as provided in the project data. Not every source has yet been independently verified. Please report errors or missing citations.
- SCIENEXY Computer Science Reference
Suggest a correction or source · More in Algorithms & Data Structures