[Python-Dev] Complexity documentation request

[Dimitrios Apostolou]

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


Thanks,
Dimitris