Static vs Dynamic Arrays

In the previous page, we claimed that dynamic arrays provide O(1) "amortized" time for append operations. But what exactly does "amortized" mean? And how can we claim O(1) when individual operations sometimes take O(n) time due to resizing?

This isn't handwaving or an approximation — amortized analysis is a rigorous mathematical technique used throughout computer science to analyze the true cost of operations in data structures with occasional expensive operations. Understanding amortized analysis transforms how you think about algorithm efficiency and is essential for evaluating any data structure with resize, rebalance, or cleanup operations.

Definition:

Amortized analysis is a method for analyzing the time complexity of a sequence of operations by averaging the total cost over all operations, even if some individual operations are expensive.

The key distinction from average-case analysis:

• Average-case analysis considers the expected cost of a single operation given random inputs
• Amortized analysis considers the actual cost of a sequence of operations, dividing total cost by number of operations

Amortized analysis is about guarantees, not probability. There's no randomness involved — we're precisely computing total work.

The intuition:

Imagine you have a monthly subscription for $120/year, billed as a single annual payment. Each month, the "amortized" cost is $10 — even though Jan 1 costs $120 and the other 364 days cost $0.

Similarly, if you append 1 million elements to a dynamic array:

• Most appends cost O(1) — just write and increment
• A few appends trigger resize and cost O(n) that resize
• Total cost divided by 1 million operations = amortized cost per operation

If total cost is O(n) for n operations, amortized cost per operation is O(n)/n = O(1).

Formal definition:

Given a sequence of n operations with individual costs c₁, c₂, ..., cₙ:

Amortized cost per operation = (c₁ + c₂ + ... + cₙ) / n

We say an operation has O(f(n)) amortized cost if the total cost of any n operations is O(n × f(n)).

The simplest amortized analysis technique is the aggregate method: compute the total cost of n operations directly, then divide by n.

Applying to dynamic array append:

Let's analyze appending n elements to an initially empty dynamic array with doubling strategy (growth factor 2).

The costs:

• Each append writes 1 element: n total writes = O(n)
• Resizes occur when capacity is exceeded

When do resizes occur?

With doubling and initial capacity 1:

• Resize at size 1 → new capacity 2 (copy 1 element)
• Resize at size 2 → new capacity 4 (copy 2 elements)
• Resize at size 4 → new capacity 8 (copy 4 elements)
• Resize at size 8 → new capacity 16 (copy 8 elements)
• ...
• Resize at size 2^k → new capacity 2^(k+1) (copy 2^k elements)

Resizes happen when size is 1, 2, 4, 8, ..., up to some 2^k where 2^k ≤ n < 2^(k+1).

Total resize cost:

Total elements copied = 1 + 2 + 4 + 8 + ... + 2^k

This is a geometric series with closed form:

1 + 2 + 4 + ... + 2^k = 2^(k+1) - 1 < 2 × 2^k ≤ 2n

So total elements copied across ALL resizes is less than 2n.

Total cost of n appends:

• n writes (one per append): n operations
• < 2n copies (across all resizes): < 2n operations
• Total: < 3n operations

Amortized cost per append:

Amortized cost = Total cost / n = 3n / n = 3 = O(1)

The geometric series insight:

The magic is in the geometric series. With doubling:

1 + 2 + 4 + 8 + ... + n/2 + n = 2n - 1

The sum of all previous terms equals less than the last term! This is why doubling works — the total cost of ALL previous resizes is bounded by the cost of one resize at the current capacity.

Another way to see it: each element is copied at most log₂(n) times across all resizes (once when array has 2 elements, once when it has 4, once when it has 8, ...). So n elements × log₂(n) copies each? No! Most elements are added late and copied few times. The average element is copied O(1) times.

The accounting method is a more intuitive approach: we assign each operation an "amortized cost" that may differ from its actual cost. The extra charge (when amortized > actual) is stored as "credit" to pay for expensive operations later.

The rule:

• Accumulated credit must never go negative
• If credit stays non-negative, amortized costs are valid upper bounds

Applying to dynamic array:

Let's assign each append an amortized cost of 3 units:

• 1 unit: to write the element (the actual cost of a simple append)
• 2 units: stored as credit for future resize

How does this pay for resizes?

Consider the moments before and after a resize from capacity c to 2c:

Before resize:

• Array has c elements (full)
• After the previous resize (at capacity c/2 → c), the array had c/2 elements
• Since then, c/2 elements were appended
• Each of those c/2 appends deposited 2 credits
• Total credits accumulated: c/2 × 2 = c

During resize:

• We must copy c elements to the new array
• Cost: c units
• We have exactly c credits stored
• Pay c credits for the c copies
• Credit balance: 0

After resize:

• New capacity is 2c, current size is c
• Next resize won't happen until size reaches 2c
• That requires c more appends
• Each of those c appends deposits 2 credits
• When next resize happens, we'll have 2c credits for 2c copies

The accounting always works out! Each element "prepays" for its future copying costs.

The accounting method conclusion:

Since we can pay for all operations (including resizes) with amortized cost 3 per append, and credits never go negative, the amortized cost per append is O(1).

This approach is often more intuitive than the aggregate method because it explicitly shows HOW the expensive operations are paid for. Each cheap operation "saves up" for the occasional expensive one.

The potential method is the most powerful (and most mathematical) amortized analysis technique. It defines a "potential function" Φ that maps data structure states to non-negative numbers, similar to potential energy in physics.

The formula:

Amortized cost = Actual cost + ΔΦ

Where ΔΦ = Φ(after) - Φ(before) is the change in potential.

• If ΔΦ > 0: operation stores potential (increases "energy")
• If ΔΦ < 0: operation releases stored potential (spends "energy")

Requirements:

• Φ(initial state) = 0
• Φ(any state) ≥ 0 (potential is never negative)

For dynamic array:

Define potential function:

Φ(array) = 2 × size - capacity

Where size = number of elements, capacity = allocated slots.

Verify the requirements:

• Initial state: size = 0, capacity = 0 or some small constant → Φ = 0 or small constant ✓
• After resize: size = capacity/2 → Φ = 2(capacity/2) - capacity = 0 ✓ (potential is released)
• At capacity: size = capacity → Φ = 2(capacity) - capacity = capacity ≥ 0 ✓
• In between: Φ = 2×size - capacity. Since size ≤ capacity, and size ≥ capacity/2 after resize, Φ is between 0 and capacity ✓

Analysis of append (no resize):

Actual cost = 1 (write the element)
ΔΦ = (2(size+1) - capacity) - (2×size - capacity)
    = 2(size+1) - 2×size
    = 2
Amortized cost = 1 + 2 = 3 = O(1)

Analysis of append (with resize from capacity c to 2c):

Before: size = c, capacity = c, Φ = 2c - c = c
After: size = c+1, capacity = 2c, Φ = 2(c+1) - 2c = 2

Actual cost = 1 (write new element) + c (copy c elements) = c + 1
ΔΦ = 2 - c = -(c-2)

Amortized cost = (c + 1) + (2 - c) = 3 = O(1)

The expensive resize cost (c copies) is exactly offset by the large decrease in potential! The potential we built up over many cheap operations is "released" during the expensive operation.

We've proven that doubling gives O(1) amortized append. Does this hold for other growth factors? The answer reveals fascinating trade-offs.

General growth factor α > 1:

With growth factor α, capacity sequence is:

c₀, αc₀, α²c₀, α³c₀, ...

For n appends, number of resizes is approximately log_α(n).

Total copying work:

c₀ + αc₀ + α²c₀ + ... + c₀αᵏ (where αᵏ ≈ n)
= c₀(αᵏ⁺¹ - 1)/(α - 1)
≈ αn/(α - 1)
= O(n) for any constant α > 1

So any constant growth factor > 1 gives O(1) amortized append!

But the constants matter:

Total copying work is approximately αn/(α - 1):

Smaller growth factors mean more resize operations and more total copying.

The space-time trade-off:

• Larger factor (2.0): Fewer resizes, less total copying, BUT more wasted space (up to 100% overhead in the worst case)
• Smaller factor (1.5): More resizes, more copying, BUT less wasted space (up to 50% overhead)
• Even smaller (1.25): Even more resizes, BUT only 25% space overhead

Why not growth factor 1.0 (adding a constant)?

With constant growth (e.g., adding 100 slots each time), the resize cost analysis breaks down:

Total copies = c₀ + (c₀+100) + (c₀+200) + ... 
            = O(n²/100) = O(n²)

This is quadratic! Linear growth does not amortize to O(1).

Understanding amortized cost has practical implications for how you use dynamic arrays:

1. Occasional latency spikes

Amortized O(1) doesn't mean every operation is fast. Resizes can cause latency spikes:

• For an array with 1 million elements, a resize copies 1 million items
• This might take milliseconds — an eternity in some contexts
• Real-time systems, game loops, or low-latency services must account for this

Mitigation strategies:

• Pre-allocate with estimated capacity: ArrayList(expectedSize)
• Perform appends during non-critical periods
• Use incremental resize techniques (rare, specialized implementations)

2. Memory allocation overhead

Each resize involves memory allocation, which has its own overhead:

• Heap allocation is not free (typically O(1) but with larger constants)
• Memory fragmentation can accumulate over many resizes
• Large allocations may trigger garbage collection in managed languages

3. Cache effects during resize

Copying all elements during resize:

• Touches potentially cold memory (elements not recently accessed)
• Pollutes CPU cache with data that might not be needed immediately
• Creates memory pressure from having two copies briefly in memory

4. When amortized analysis fails you

Amortized analysis assumes you perform many operations. If you:

• Append only a few elements then discard the array
• Trigger a resize just before a critical section
• Care about worst-case latency for every operation

The amortized perspective may not reflect your actual experience. The expensive operations, though rare, do happen.

5. Capacity hints are valuable

Most dynamic array implementations allow specifying initial capacity:

arr = []  # Default capacity, will resize on growth
arr = [None] * 1000  # Pre-allocated for 1000 elements

If you know approximately how many elements you'll add, pre-allocating can eliminate all resizes, turning amortized O(1) into actual O(1).

The amortized analysis techniques we've learned apply to many data structures. Understanding this pattern helps you recognize and analyze similar situations.

Hash tables:

Hash tables resize when the load factor exceeds a threshold. The analysis is nearly identical to dynamic arrays:

• Geometric growth on resize (typically double)
• O(n) work during resize (rehash all elements)
• O(1) amortized insertion

Splay trees:

Splay trees move accessed nodes to the root, occasionally requiring O(n) rotations. Through potential function analysis, operations are O(log n) amortized.

Union-Find with path compression:

Each operation might walk a long path, but the work "flattens" the structure for future operations. Amortized analysis (using inverse Ackermann function) proves near-O(1) operations.

Fibonacci heaps:

DecreaseKey is O(1) amortized despite occasionally triggering cascading cuts. Potential function tracks trees and marked nodes.

We have developed a rigorous understanding of amortized analysis and its application to dynamic arrays. Let's consolidate the key insights:

What's next:

We've now analyzed both static and dynamic arrays, plus the amortized cost of dynamic array operations. The final page synthesizes everything: Trade-offs between Static and Dynamic Arrays — when to choose which, and how to make informed engineering decisions based on your specific constraints.