[Python-Dev] Complexity documentation request

[Greg Ewing]

Dimitrios Apostolou wrote:

> On the other hand notes could be added for various oddities according to 
> experience. For example that for sets up to 10(?) elements, a list would 
> probably be better because of the hashing overhead.

That's the sort of thing that tends to be *very*
implementation dependent -- not just between CPython
and others, but between different releases of CPython.

> Hmmm, the first thing that comes to mind is prepending an item in a list 
> which is small and seems nice, but is O(n) I think!

Yeah, there's no substitute for having at least a
rough idea of how the object you're using is implemented,
e.g. array vs. linked list.

This kind of very basic information is something that
I think ought to be documented, and some guarantees
made in the language definition. For example, I think
a Python implementation that implemented lists as
linked lists would make many people unhappy, as their
algorithms suddenly went from O(n**m) to O(n**(m+1))
without anyone telling them.

-- 
Greg