A dynamic array that doubles its capacity when full has constant amortized append cost. Although an individual append can require Θ(n) time when resizing and copying occur, the total work across n appends is Θ(n).
Amortized Dynamic Array Append Cost
A dynamic array that doubles its capacity when full has constant amortized append cost. Although an individual append can require Θ(n) time when resizing and copying occur, the total work across n appends is Θ(n).
\(T_{\mathrm{amortized}}(n) = \Theta(1) per append; T_{\mathrm{total}}(n) = \Theta(n)\)
What this formula means
Scientific principle
Principle
Dynamic arrays use spare capacity to avoid resizing after every insertion. When capacity is exhausted, the array allocates a larger storage region and copies existing elements. With geometric capacity growth, expensive resizing operations become increasingly infrequent.
Derivation
1. Begin with an empty dynamic array and assume capacity doubles whenever the array becomes full.
2. Ordinary append operations write one element and take Θ(1) time.
3. Resizing from capacity 1 to 2 copies 1 element; resizing from 2 to 4 copies 2 elements; resizing from 4 to 8 copies 4 elements.
4. Across n appends, the total number of copied elements is bounded by 1 + 2 + 4 + ⋯ + 2ᵏ, where the largest copied capacity is less than n.
5. This geometric series is less than 2n.
6. The n ordinary element writes contribute another n operations.
7. Therefore, total work is bounded by approximately 3n, giving Θ(n) total work and Θ(1) amortized work per append.
Final Result
T_amortized(n) = Θ(1)
Total Cost
T_total(n) = Θ(n)
Aggregate Bound
T_total(n) < 3n under the simplified unit-cost doubling model
Capacity Growth
C_new = 2C_old
Variables and their meanings
| Symbol | Meaning | Unit |
|---|---|---|
T_amortized(n) | Average cost per append over a sequence of operations | Abstract operation cost |
T_total(n) | Total cost of n append operations | Abstract operation cost |
n | Number of appended elements | Elements |
C_old | Array capacity before resizing | Slots |
C_new | Array capacity after resizing | Slots |
SI units and conversions
Amortized Cost
Abstract operation cost per append
Total Cost
Abstract operation count
Capacity
Slots
Complexity
Θ(1) amortized per append
Conditions of use
The dynamic array increases capacity geometrically when full.
The standard doubling policy uses C_new = 2C_old.
Copying one element and appending one element are treated as constant-cost operations.
The analysis considers a sequence of append operations rather than a single isolated append.
The array has sufficient addressable memory for the required resizing operations.
Limitations and assumptions
A single append that triggers resizing can still take Θ(n) time.
Amortized constant time is not the same as constant worst-case time for every individual append.
The exact constant factors depend on allocation, copying, and memory-management costs.
The analysis does not directly include synchronization costs in concurrent dynamic arrays.
Capacity policies other than geometric growth can produce different amortized costs.
Step-by-step worked examples
| Problem | Solution | Answer |
|---|---|---|
A dynamic array starts with capacity 1 and doubles whenever full. Estimate the total number of copied elements when appending 8 elements. |
| The array copies 7 existing elements during resizing and performs 8 ordinary writes, for approximately 15 simplified operations. |
A dynamic array performs 1,000 append operations under a doubling policy. Use the simplified aggregate bound to estimate the total work and amortized cost. |
| The simplified total-work bound is below 3,000 operations, giving a constant amortized cost below 3 abstract operations per append. |
Real-world applications
Dynamic array implementations
ArrayList-style collections
Vector data structures
Resizable buffers
Dynamic storage in programming languages
Formula Meaning
A dynamic array that doubles its capacity when full has constant amortized append cost. Although an individual append can require Θ(n) time when resizing and copying occur, the total work across n appends is Θ(n).
Sources and further reading
No source has been supplied for this item yet. Treat the claim as needing editorial verification.