[Python-Dev] Complexity documentation request

Sun Mar 9 07:28:02 CET 2008

Hello all,
Is it possible to include algorithm complexity information for the various 
built-in types (strings, sets, lists, dictionaries...)? This would ease 
the decision for choosing the correct type. The information could simply 
be added as a new column in the tables found on pages as the following:
http://docs.python.org/lib/types-set.html
http://docs.python.org/lib/typesseq.html
It took me a while to find some information for my purposes, however I'm 
not sure whether it's outdated or incomplete. The best sources I found are 
python-list archive and a PEP:
http://www.python.org/dev/peps/pep-3128/
http://mail.python.org/pipermail/python-list/2007-June/446877.html
Nevertheless, algorithm complexity is not always the answer. I remember 
some years ago I preferred using "x in list" rather than "x in set" as 
member checking in a tight loop, because the list was rather small (10-20 
elements) and the overhead for the set was far greater than the better 
algorithm complexity advantage. So if this information is available, it 
would be nice to document constant time factors too. :-)
Thanks in advance,
Dimitris