✦ScienexySCIENCE KNOWLEDGE LIBRARY
concept · INFO-CS-ADS-024

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

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.

Variables

SymbolMeaningUnit

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

QuestionAnswer

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