In this link I see following:
A recent talk about unordered_map in C++ made me realize, that I should use unordered_map for most cases where I used map before, because of the efficiency of lookup ( amortized O(1) vs. O(log n) ).
In dictionary it says: amortize: to gradually reduce or write off the cost or value of (as an asset).
But I'm still not sure what does "amortized" mean here.
Amortize as used in the referenced stackoverflow question has a technical meaning that ordinarily is explained in several lectures of an analysis-of-algorithms course, vs being explained in ELU. The general idea is that operations are accounted for in such a way that an algorithm can be proven to have a certain complexity, not in the worst case, but on the average. Amortized cost of algorithmic steps is the cost per step when the total cost is spread out over all the steps.
For example, an algorithm might typically use O(1) time to do each of many operations, but suppose that at some point in any sequence of N operations an operation must be done that takes O(N log N) time. That cost, when spread out over the N operations, amounts to an extra O(log N) time per operation, resulting in amortized complexity of O(1 + log N), which is O(log N).
