List insertion cost

[Robert Kern]

On 2009-07-21 14:21, Lucas P Melo wrote:
> Hello,
> 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). Python lists are contiguous arrays in memory, and everything after the 
insertion point needs to be moved. Raymond Hettinger has a good talk about the 
implementation of Python lists and other container objects.

http://www.youtube.com/watch?v=hYUsssClE94
http://www.pycon.it/static/stuff/slides/core-python-containers-under-hood.ppt

-- 
Robert Kern

"I have come to believe that the whole world is an enigma, a harmless enigma
  that is made terrible by our own mad attempt to interpret it as though it had
  an underlying truth."
   -- Umberto Eco