[Python-Dev] Complexity documentation request

["Martin v. Löwis"]

> I just created a very basic one at
> http://wiki.python.org/moin/TimeComplexity?action=show

I just knew that this could be a field of endless nitpicking.

I think the dict.copy classification is incorrect. A dict.copy
can take unbounded time, if the dict has seen many recent
deletions (which didn't shrink it). Copying will have to iterate
over all slots of the dictionary, and the ratio of slots to
keys can grow unbounded if you have just deletions without
insertions.

IOW, if you do

d = {}
for i in xrange(N):
   d[i]=i
for i in xrange(N-1):
   del d[i]

then doing

d.copy()

takes O(N), not constant time (even though there is only
one key in the dictionary).

> I wasn't sure about many of the set() operations, so I didn't include those.

set is just implemented like a dictionary, without keys.

Regards,
Martin