[Python-Dev] Complexity documentation request (original) (raw)

Greg Ewing greg.ewing at canterbury.ac.nz
Sun Mar 9 20:50:02 CET 2008

Aahz wrote:

* Other Python implementations (Jython, PyPy, IronPython) may not be able to provide the same type implementations

* Algorithmic information does sometimes change between versions, and keeping the docs updated is not trivial

Still, I think there are some general expectations one should be able to have of any implementation, e.g. that accessing a list item is roughly O(1), and not O(n) as it would be if they were implemented as linked lists.

Dict access should probably be documented as no worse than O(log n) to allow for tree implementations.

-- Greg

More information about the Python-Dev mailing list