✦ScienexySCIENCE KNOWLEDGE LIBRARY
General science · SCI-FORM-COM-2074

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

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).

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

SymbolMeaningUnit

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

ProblemSolutionAnswer

A dynamic array starts with capacity 1 and doubles whenever full. Estimate the total number of copied elements when appending 8 elements.

  • The capacity sequence is 1, 2, 4, 8.

  • The resizing operations copy 1 element, then 2 elements, then 4 elements.

  • Total copied elements = 1 + 2 + 4 = 7.

  • There are also 8 ordinary element writes.

  • Simplified total work = 7 + 8 = 15 operations.

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.

  • Given: n = 1,000.

  • Use the simplified bound: T_total(n) < 3n.

  • T_total(1,000) < 3 × 1,000.

  • T_total(1,000) < 3,000 abstract operations.

  • Amortized cost < 3,000/1,000.

  • Amortized cost < 3 abstract operations per append under this accounting model.

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.

← Back to Formula Hub · Suggest a correction or source