Difference in complexity of append and concatenate

Question

Consider below methods for forming a list of thousand numbers.

def test1():
    l = []
    for i in range(1000):
        l = l + [i]
    return l


def test2():
    l = []
    for i in range(1000):
        l.append(i)    

print timeit.repeat(stmt=test1, number=100,repeat=2)
print timeit.repeat(stmt=test2, number=100,repeat=2)

Output:

[0.30474191033602543, 0.3783786557587963]
[0.015134341605235302, 0.023081246200096328]

Why is the append method around 20 times better than concatenation. AFAIK append has O(1) complexity while concatenation has O(k) complexity. While K here is 1.

Is there some obvious thing I overlooked?

Answer 1

You are creating a new list object each time by concatenating. This requires copying all elements from the old list into a new one, plus one extra. So yes, using l = l + [i] is an O(N) algorithm, not O(1).

At the very least, don't use + concatenation; use += augmented concatenation, which is the same thing as list.extend() with a re-assignment to the same reference:

def test3():
    l = []
    for i in range(1000):
        l += [i]  # or use l.extend([i])
    return l

This produces:

>>> print timeit.repeat(stmt=test1, number=100, repeat=2)
[0.1333179473876953, 0.12804388999938965]
>>> print timeit.repeat(stmt=test2, number=100, repeat=2)
[0.01052403450012207, 0.007989168167114258]
>>> print timeit.repeat(stmt=test3, number=100, repeat=2)
[0.013209104537963867, 0.011193037033081055]