However, I have to agree with the substance of the comment; it is a pretty lousy explanation of amortized performance to simply equate it with a kind of average:
> If you read more about big-O, you may see the word “amortized” thrown around. That’s a fancy word for “average,” meaning that individual occurrences don’t all behave exactly the same, but over the long run, averaging over many operations, the behavior has a certain characteristic.
While the result of amortized analysis gives us a kind of average, averages show up in more than way in performance analysis not necessarily via amortization.
The author complains that "[Pyon] pointed out a detail of algorithmic analysis that I had not mentioned. It’s a detail that I had never encountered before."
But the author obviously encountered amortization before, and mentioned it in the article, and not in a very good way.
Amortized analysis isn't something obscure; it is the basis for understanding everyday algorithms such as chained hash tables and garbage collection. It's covered in like third year CS courses.
When an algorithm touts amortized performance, that's a red flag: it suggests that certain operations are infrequently hit with a pretty big cost. For example, a hash table insertion that has to resize the table doesn't just not act "exactly the same" as a previous insertion, or following one; it takes much longer. All the items inserted so far (or at least their hash table entries) have to be visited to redistribute them to a larger table. That could be hundreds of millions: the larger the table, the more expensive this is, yet less frequent. So yes, the amortized performance (like O(1) constant time for hash table insertions) is a kind of average, but the distribution may be heavily skewed, with implications particularly for real-time work. It's not a "nice" average with a tight bell curve distribution jittering around a mean.
A better way would be to say that "amortized" is a kind of average where operations are infrequently penalized with a substantial performance hit, which helps make most other operations faster: the "amortized analysis" which calculates this kind of average works by pretending to redistribute the large cost incurred by one operation among the others. And not all average performance figures are derived using amortized analysis. The word is only used when that particular reasoning was applied, and is mentioned as kind of warning label.
An example of average that is not amortized is, say, searching an unordered list of unique keys, where we expect on average successful search for a random key to process half the list. Readers do deserve to know that they should not use the word "amortized" for this kind of average!
[–] nedbat 9 hours ago
[–] kazinator 9 hours ago
Operations can incur some kind of "debt" which a more expensive operation occurring later has to pay for. Or they can be regarded as enjoying something "prepaid" by an earlier expensive operation until the credit runs out and another prepayment has to be made. Possibly, either view can be used to arrive at the same result.
The level of contention on the part of Pyon is disconnected from the level of detail given to "amortized" in the article and based on the false premise that the word "average" implies some kind of order that is contrary to "amortized". (Expert, my foot).
It is factually correct that a an amortized performance is an average, but readers should be aware that it's a special kind of average (not every average is "amortized") and that it is a warning label: an algorithm with performance quoted as amortized possibly exhibits a big latency spike that occurs infrequently.
I think you are being very generous to call his comment "obvious humor". A number of the people in that comment stream missed the humor, and pyon gave no indication (such as a tone indicator) that it was humor.