Amortized Analysis

Also Known As

TL;DR

Explanation

Some operations are occasionally expensive but rarely so. Amortized analysis spreads the cost: a dynamic array doubles capacity when full — a resize is O(n) but happens so rarely that over n appends the average is O(1). The accounting method assigns 'credits' from cheap operations to pay for future expensive ones. PHP's array[] = $item is amortized O(1) for the same reason. Amortized != average: average considers random inputs; amortized considers worst-case sequences. The difference matters when budgeting for occasional spikes.

Common Misconception

Why It Matters

Common Mistakes

• Confusing amortized O(1) with worst-case O(1) — occasional spikes still happen.
• Using dynamic arrays in hard real-time systems — the O(n) resize spike causes deadline misses.
• Not understanding that PHP unshift/shift are O(n) NOT O(1) amortized — they reindex every time.
• Assuming stack operations are always cheap — SplStack push/pop are O(1) amortized, but array_shift is O(n).

Avoid When

• Do not use amortized O(1) as a guarantee for real-time or latency-sensitive systems — the occasional O(n) resize still happens.
• Avoid citing amortized cost when your workload triggers worst-case operations systematically (e.g. always inserting at max-load).

When To Use

• When evaluating data structures whose worst-case single operation cost is misleading (dynamic arrays, hash table rehashing, splay trees).
• When choosing between two structures with similar average performance — amortized cost reveals the true cost per operation over a sequence.
• When documenting API complexity guarantees to callers who care about throughput rather than single-call latency.

Code Examples

// Mistaking amortized for guaranteed:
function realtimeTask(SplDoublyLinkedList $queue): void {
    // In a 16ms real-time frame:
    $queue->push($data); // Usually O(1)... but occasionally O(n) on resize
    // Frame budget exceeded! Dropped frame in a game/audio context
}

// Understand what 'amortized O(1)' means:
// For N total pushes to a dynamic array:
// - ~N pushes are O(1)
// - log(N) resizes are O(N) each
// Total: O(N) for N operations = O(1) amortized

// Pre-allocate to avoid all resize overhead:
$spl = new SplFixedArray(10000); // O(1) guaranteed access, no resize
for ($i = 0; $i < 10000; $i++) {
    $spl[$i] = $data[$i]; // Always O(1) — no resize possible
}

References

• ↗ https://en.wikipedia.org/wiki/Amortized_analysis

Tags

Related Terms