Take the 2-minute tour ×
English Language & Usage Stack Exchange is a question and answer site for linguists, etymologists, and serious English language enthusiasts. It's 100% free, no registration required.

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.

share|improve this question
    
    
This is a CS.SE question. See Basics of Amortized Analysis -- amortized here has a technical meaning which is related, but not identical, to the dictionary definition. –  Andrew Leach Nov 21 '13 at 7:29

1 Answer 1

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).

share|improve this answer
    
Thank you. That's an interesting metaphor usage. –  John Lawler Nov 21 '13 at 13:52

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.