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

Daniel Stutzbach daniel at stutzbachenterprises.com
Sun Mar 9 23:17:53 CET 2008

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

More information about the Python-Dev mailing list