List insertion cost

[Daniel Stutzbach]

On Tue, Jul 21, 2009 at 2:21 PM, Lucas P Melo <lukepadawan at gmail.com> wrote:

> I would like to know how much it costs to insert an element into a list
> using this operation:
> a[2:2] = [ 1 ]
> i. e, what is the complexity of the operation above (given that len(a) =
> n)?
>

O(n)

If you want O(log n), you can use the blist extension type from
http://pypi.python.org/pypi/blist/

--
Daniel Stutzbach, Ph.D.
President, Stutzbach Enterprises, LLC <http://stutzbachenterprises.com>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.python.org/pipermail/python-list/attachments/20090721/4f40afaf/attachment.html>