[Python-Dev] Complexity documentation request

[Daniel Stutzbach]

On Sun, Mar 9, 2008 at 4:43 PM, Guido van Rossum <guido at python.org> wrote:
>  Well, there you have hit the nail on the head -- should we document
>  the actual or the guaranteed O() expression?

Either.  Both.  Put a note at the bottom saying that factors of O(log
n) have been dropped and they're basically the same thing (this is
sometimes called "Soft O notation").  Big O is technically an
upper-bound anyway.  When was the last time a new version caused a
function to become slower by more than a factor of O(log n)?

As is, some operations *are* documented, but in odd places.  For
example, the documentation for deque describes the complexity of some
of the list type's operations.

-- 
Daniel Stutzbach, Ph.D.             President, Stutzbach Enterprises LLC