amortized cost versus average-case cost
Two ideas are constantly confused because both involve 'averaging': amortized cost and average-case cost. They sound alike but rest on completely different foundations. Amortized cost averages the work over a sequence of operations and makes no assumption about probability; average-case cost averages over a distribution of random inputs and is fundamentally about probability. Mixing them up leads to claims that are either too strong or simply meaningless.
Average-case analysis asks: if the input is drawn at random from some assumed distribution, what is the expected running time? Its answer depends entirely on that assumed distribution — change the distribution and the average changes, and a worst-case input can still be slow. Randomized quicksort, for instance, runs in O(n log n) EXPECTED time over its own coin flips, but its worst case is still O(n^2). Amortized analysis asks something with no randomness at all: over the worst possible SEQUENCE of operations chosen by an adversary, what is the total work divided by the number of operations? Its O(1)-per-operation guarantee holds for every sequence with certainty — there is no probability distribution and no expectation. A dynamic array's append is amortized O(1) as an ironclad fact about any append sequence; it is not 'O(1) on average inputs.'
The practical difference is about what guarantee you are buying. An amortized bound is a deterministic promise: total work over the sequence is bounded, no matter what, though an individual operation can spike. An average-case bound is a probabilistic statement: typical inputs are fast, but an unlucky or adversarial input can be slow. A subtle bridge: when an algorithm is randomized, people sometimes compute 'expected amortized cost,' which combines both — averaging over coin flips AND over a sequence — but that is a deliberate combination, not the same thing as either alone. The honest rule of thumb: if the claim mentions a distribution or expectation, it is average-case; if it bounds the total over a worst-case sequence with no probability, it is amortized.
Dynamic-array append is amortized O(1): a guarantee for every sequence, no randomness. Randomized quicksort is average-case (expected) O(n log n): true over its coin flips, but a specific run can still hit O(n^2). The first is certain for all inputs; the second is a probability statement that an unlucky run can violate.
Amortized = deterministic average over a worst-case sequence; average-case = expected over a random input distribution. Different guarantees entirely.
An amortized bound has no probability in it and holds for every sequence; an average-case bound depends on an assumed input distribution and can be violated by a bad input. Calling an amortized result 'average-case' (or vice versa) is a real error, not a wording quibble.