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 -- http://mail.python.org/mailman/listinfo/python-list
