Ah, those weasel words. What's the difference between "linear" and "amortized liner"?
An unamortized estimate is an estimate made for individual samples. For
example, a linear unamortized estimate for the find() generic algorithm
indicates that each call to find() should exhibit behavior liner in the
input size (let us assume).
An amortized estimate is an estimate made for a sequence of samples; in
that sense, an amortized estimate) is like an average. For example, a linear
amortized estimate for push_back() indicates that occasionally a call to
push_back() may exhibit super-linear behavior, but with enough calls to
push_back() the overall behavior becomes linear.
This page last modified on 12 February 2004.