How it works
A queue built from two stacks moves each element at most once, so although one transfer is linear, the average cost per operation is constant.
Argue amortised cost by counting total work across a sequence, not the worst single operation.
Common error
Reporting the worst single operation as the cost, which misses the whole point of amortisation.
Worked example
Example
Dynamic array capacities: 1, 2, 4, 8, ...
A full array triggers allocation and copying
Most appends write one element
An individual resize append may cost O(n)Amortised cost describes a sequence of operations. With geometric capacity growth, expensive copies are spread over many cheap appends, giving constant amortised append cost even though an individual resize is linear.
Exercises
4.4.1 · Explain
When growing capacity by doubling, how many elements are copied across expansions from capacities 1, 2, and 4?
Show solution
The copies total 1 + 2 + 4 = 7. The geometric sum remains proportional to the number of appended elements.
4.4.2 · Explain
Why is constant amortised time different from constant worst-case time?
Show solution
Amortised time bounds the average cost across a sequence. It permits an occasional expensive operation, so it does not promise every individual operation is constant-time.