Why l.insert(0, i) is slower than l.append(i) in python?

Question

I tested two different ways to reverse a list in python.

import timeit

value = [i for i in range(100)]
def rev1():
    v = []
    for i in value:
        v.append(i)
    v.reverse()

def rev2():
    v = []
    for i in value:
        v.insert(0, i)

print timeit.timeit(rev1)
print timeit.timeit(rev2)

Interestingly, the 2nd method that inserts the value to the first element is pretty much slower than the first one.

20.4851300716
73.5116429329

Why is this? In terms of operation, inserting an element to the head doesn't seem that expensive.

Answer 1

insert is an O(n) operation as it requires all elements at or after the insert position to be shifted up by one. append, on the other hand, is generally O(1) (and O(n) in the worst case, when more space must be allocated). This explains the substantial time difference.

The time complexities of these methods are thoroughly documented here.

I quote:

Internally, a list is represented as an array; the largest costs come from growing beyond the current allocation size (because everything must move), or from inserting or deleting somewhere near the beginning (because everything after that must move).

Now, going back to your code, we can see that rev1() is an O(n) implementation whereas rev2() is in fact O(n2), so it makes sense that rev2() will be much slower.