amortized time complexity

A set of operations on a data type is said to have amortized time complexity f(n) for n operations if any sequence of n (legal) operations on it can be executed in time n f(n). This precisely means that the average time to execute any operation in the sequence is f(n).

• This is not the same as giving a worst case time complexity for every operation: the data type may "save" time on some operations, by performing them in considerably less time than f(n), and use the slack it's gained by performing other operations in time much greater than f(n).
• Nor is it the same as expected time complexity. There is no model here of a "typical" input sequence, or even a probability distribution on possible inputs. The data type guarantees the average time to execute any sequence of n operations is n f(n).