[Python-Dev] Complexity documentation request

[Dimitrios Apostolou]

Daniel Stutzbach wrote:
> I just created a very basic one at
> http://wiki.python.org/moin/TimeComplexity?action=show

Hi,

Just one quick note. What exactly do you mean by "Amortized worst case"? 
Shouldn't it just be "Worst case"? I think that the word "amortized" 
better describes the time complexity of specific operations.

For example  I think that the insertion in a dictionary should be noted 
as "O(1) amortized" for the average case meaning that when doing 
infinite random insertions, the time asymptotically tends to be 
constant. And worst case is simply O(n), not amortized. Am I missing 
something?


Thanks,
Dimitris