array, list, performance...

[Steve Holden]

"Christopher Armstrong" <radix at twistedmatrix.com> wrote in message
news:mailman.1023373030.31871.python-list at python.org...
>
> > Michael Chermside <mcherm at destiny.com> writes::
> >   li[n] = x      assignment to the middle is O(len(li))
>
> This doesn't seem right. Shouldn't that be O(1), just like
> access-time?
>

If you can do it in O(1) you should go work for Zope corporation :-)

The problem is the need to make a new entry in the middle of the existing
structure. This can involve memory allocation and value copying, etc.

regards
-----------------------------------------------------------------------
Steve Holden                                 http://www.holdenweb.com/
Python Web Programming                http://pydish.holdenweb.com/pwp/
-----------------------------------------------------------------------