[Python-Dev] Complexity documentation request

Wed Mar 12 19:26:31 CET 2008

On Mon, Mar 10, 2008 at 12:05 PM, Daniel Stutzbach
<daniel at stutzbachenterprises.com> wrote:
> On Sun, Mar 9, 2008 at 9:22 AM, Aahz <aahz at pythoncraft.com> wrote:
> > There probably would be some value in a wiki page on python.org that
> > provides this information, particularly across versions. You may be
> > able to find volunteers to help on comp.lang.python.
>> I just created a very basic one at
> http://wiki.python.org/moin/TimeComplexity?action=show
>> I'm not that familiar with the Wiki syntax, so the tables are kind of
> ugly at the moment.
>> I wasn't sure about many of the set() operations, so I didn't include those.

For python's purposes, I think it's simpler to classify an operation
as either "linear" or "near constant", then have an explanation that
"near constant" is only the typical performance (it doesn't make
guarantees about worst case behaviour), may include O(log n)
implementations, etc. That suffices to distinguish use cases, and
anything more specific may be dominated by constant factors anyway.
Something like sort is a special case. I don't think the languages
needs to guarantee any particular performance, yet it's worth
documenting that CPython has a rather good implementation.
-- 
Adam Olsen, aka Rhamphoryncus