# Deleting the first element of a list

Thu Oct 3 23:30:07 CEST 2002

```On Wednesday 02 October 2002 21:26, Bruce Dawson wrote:
>
> Highly applicable to this thread. Deleting the first item of a Python
> list or C++ vector is an O(n) operation - proportional to the number
> of items in the list. If you do that for every item in the list it is
> O(n^2) - proportional to the square.

Just for fun, I wrote this up:

N = 17
M = 5
for n in xrange(4,N):
m = 5
avg = 0
for j in xrange( M ):
l = range( 2**n )
start = time.time()
for i in xrange( 2**(n-3) ):
del l[ 0 ]
del l[ 0 ]
del l[ 0 ]
del l[ 0 ]
del l[ 0 ]
del l[ 0 ]
del l[ 0 ]
del l[ 0 ]
end = time.time()
avg = avg + (end - start)
avg = avg / m
print "avg time to delete list of length %10d: %.13f secs" % (2**n,
avg)

Here are the results on my machine:
avg time to delete list of length         16: 0.0000482082367 secs
avg time to delete list of length         32: 0.0000820159912 secs
avg time to delete list of length         64: 0.0001710176468 secs
avg time to delete list of length        128: 0.0003101825714 secs
avg time to delete list of length        256: 0.0006976127625 secs
avg time to delete list of length        512: 0.0017696142197 secs
avg time to delete list of length       1024: 0.0053425788879 secs
avg time to delete list of length       2048: 0.0166998147964 secs
avg time to delete list of length       4096: 0.0555817842484 secs
avg time to delete list of length       8192: 0.2105991840363 secs
avg time to delete list of length      16384: 0.9571284055710 secs
avg time to delete list of length      32768: 3.1392956018448 secs
avg time to delete list of length      65536: 25.6988666057587 secs

The last line I think shows the some effects of cache thrashing (but
not swapping; I have 1 Gig of RAM).  It also illustrates each doubling
of the problem set increases the running time by a factor of 4 or more
(ie. ~ O( N^2 ) growth, at least when the lists start to get long (ie.
> 512 items or so)

And if I change the 'del l[ 0 ]' to 'del l[ -1 ]':
avg time to delete list of length         16: 0.0000484228134 secs
avg time to delete list of length         32: 0.0000805854797 secs
avg time to delete list of length         64: 0.0001428127289 secs
avg time to delete list of length        128: 0.0002708435059 secs
avg time to delete list of length        256: 0.0005234003067 secs
avg time to delete list of length        512: 0.0010224103928 secs
avg time to delete list of length       1024: 0.0020072221756 secs
avg time to delete list of length       2048: 0.0040839672089 secs
avg time to delete list of length       4096: 0.0080970048904 secs
avg time to delete list of length       8192: 0.0164772510529 secs
avg time to delete list of length      16384: 0.0334905624390 secs
avg time to delete list of length      32768: 0.0808611869812 secs
avg time to delete list of length      65536: 0.1617539882660 secs

Here a doubling of list length leads more or less to a doubling of
running time (ie.  O( N )).

So, no real surprises, but illustrative for those who have never
compared O( N^2 ) to O( N ) algorithms before (hmmm, maybe that should
be phi( N ) or even o( N )? )  I didn't dare do a longer list for 'del
l[ 0 ]', whereas 'del l[ -1 ]' scales easily to much longer lists.

--