A slow operation does not necessarily make a data structure slow to use. Amortized analysis measures the total cost of a sequence of operations and divides it across those operations. The question is not whether every call is cheap, but whether expensive calls happen often enough to dominate the total. section 2.4
A queue made from two stacks
An immutable queue can enqueue onto one stack and dequeue from another. When the dequeue stack runs out, reversing an enqueue stack of n items costs O(n) time and space. Yet an item is pushed and popped only twice on its way through the queue. Those four constant-time actions give O(1) amortized cost per enqueue or dequeue. Equivalently, a reversal is followed by n cheap dequeues: O(n) work spread across roughly n calls. section 2.4
The qualification matters: amortized O(1) is not worst-case O(1). Persistence also changes which sequences are possible. Enqueue 100 items, perform a costly dequeue, undo to the earlier queue, and repeat that same dequeue. Each attempt reverses the same stack again; no run of cheap dequeues pays for it. If that pattern matters, options include choosing a structure with a better worst case or memoizing the reversal at a memory cost. section 2.6.3
Make the expensive case rarer—and smaller
In an immutable deque, pushes and pops usually update shallow levels. Two-thirds update one level, two-ninths update two, and progressively fewer reach deeper levels. Averaging those costs gives O(1) amortized time, while even a worst-case push or pop takes only O(log₃ n) time and extra space. Allowing two-item groups in the middle changes the depth bound to O(log₂ n), but leaves amortized pushes and pops O(1). section 3.5 section 3.8
The same distinction appears when generating lexicographic permutations of n distinct items. A call can require O(n) comparisons and swaps, but across all n! permutations, cheap calls predominate: the averages are three comparisons and 1.5 swaps per permutation, yielding O(1) amortized time. Always state the sequence over which the average is taken. section 6.2.1
Listing 6.17 An elegant recursive method for generating combinations
static IEnumerable<IDeque<int>> Combinations2(int n, int k)
{
if (k > n || k < 0)
yield break; #1
if (k == 0)
{
yield return Deque<int>.Empty; #2
yield break;
}
foreach (var r in Combinations2(n - 1, k)) #3
yield return r;
foreach (var r in Combinations2(n - 1, k - 1)) #4
yield return r.PushRight(n-1);
}
The recursive combination generator shows why a cheap component operation is not the whole algorithm: each result uses k deque pushes at O(1) amortized cost apiece, yet recursion makes the overall worst-case bound O(n) per combination. section 6.3.1
