[Python-Dev] Complexity documentation request

Dimitrios Apostolou jimis at gmx.net
Thu Mar 13 09:16:26 CET 2008

Daniel Stutzbach wrote:
> On Wed, Mar 12, 2008 at 2:52 PM, Dimitrios Apostolou <jimis at gmx.net> wrote:
>>  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.
> http://en.wikipedia.org/wiki/Amortized_analysis

Thanks for this, I understand now what it means. However given that for 
the list and deque types both columns have exactly the same values, 
wouldn't it be more useful if we simply mentioned the worst case in the 
second, or another, column?

On another note which sorting algorithm is python using? Perhaps we can 
add this as a footnote. I always thought it was quicksort, with a worst 
case of O(n^2).


More information about the Python-Dev mailing list