List insertion cost

[Lucas P Melo]

Robert Kern wrote:
> 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 
>
Thanks. :)