[Python-Dev] Complexity documentation request

["Martin v. Löwis"]

> I will open this can and say that average case complexity is the most 
> important. For example sorting O(nlogn) and dict lookup O(1).

I would still debate the complexity of dict lookup. What are you 
averaging over? In absence of any distribution property of hash
functions in the average case, you can't say anything about dictionary
performance.

I also disagree that the average complexity is "most important".
I find the worst-case complexity most important. For average-case
complexity, I just measure my application, and don't care about
theoretical numbers.

> Notes are nice and already exist at random places in the *huge* 
> documentation archive. But I still believe that the best place for this 
> are the already existing tables in the docs (I pointed them at my 
> initial post). One should trivially be able to find this information.

Feel free to start a Wiki page then. With the right keywords on the
page, it shouldn't take long for Google to pick up the page, and
return it to people asking the right questions.

> I agree that CPython docs should document CPython behaviour.

Actually, no. The "CPython documentation" documents Python, the 
language, and its standard library. It is a specification that CPython
conforms to (hopefully).

There might be fragments in it that are both worthwhile-to-mention
and implementation-specific, but they should be marked as the latter.

> 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! And besides that, 
> for someone who *cares* about his code good looks is not enough...

Define "small". For a theoretically-reasonable definition of "small",
prepending is O(1): namely, when a "small" list is one whose size
is bounded by some upper bound (say, M). For such a list, prepending
is O(1) (namely, not more than M copies). Of course, you can only
prepend a finite number of times to such a list, unless you also
delete in-between. Over a long series of insertions and deletions,
prepending will be O(1) (if M is large, with a large factor).

Regards,
Martin