On Mon, Mar 10, 2008 at 12:05 PM, Daniel Stutzbach <daniel@stutzbachenterprises.com> wrote:
On Sun, Mar 9, 2008 at 9:22 AM, Aahz <aahz@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