Why does adding to the front of the list take quadratic time?

Question

This code sample takes Big O of (N^2)

results = []

for i in range(1000000)
    result = [f(i)] + results

This code sample takes Big O of (N)

results = []

for i in range(1000000)
    result = results + [f(i)]

Why is there such a distinct difference in the Big O of these two algorithms, the only difference is that one is added to the front of the list while the other is added to the back of the list?

Does this hold true for Java, also?

"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)." - https://wiki.python.org/moin/TimeComplexity#list — jonrsharpe, May 01 '14 at 16:02
Both of these are O(N^2). `for i in xrange(1000000): results += [f(i)]` is O(N) — Paul Hankin, May 01 '14 at 16:06
Actually, neither are O(N^2) in the current code because `result` is only ever one element long and `results` is always the empty list. Neither statement is reassigning the `results` variable. — b4hand, May 01 '14 at 20:19
[dupe](http://stackoverflow.com/questions/7776938/python-insert-vs-append)? — Noelkd, May 02 '14 at 09:10

score 7 · Answer 1 · answered May 01 '14 at 16:02

7

Because lists are optimized for appending, not prepending: if you prepend, the entire list needs to be recreated.

If you want a datastructure that can append at both ends with equal efficiency, use collections.deque.

answered May 01 '14 at 16:02

Daniel Roseman

588,541
66
880
895

2

The list isn't recreated, all the elements are merely moved upward in memory to make room at the beginning, but it's still quadratic. – kindall May 01 '14 at 16:07
That depends, the elements can only be moved if there is actually space at the end of the array. – b4hand May 01 '14 at 16:28
I like this answer, and one should infer that this applies specifically to python, but a user could be led to believe that this applies to all lists in all implementations, which isn't true. Could you note that this is specific to the python implementation? – zero298 May 01 '14 at 19:20

b4hand · Answer 2 · 2014-05-09T15:31:46.720

The reason this is the case is because CPython is implemented in C and uses C arrays as the backing store for lists, and you must reallocate and move the elements before adding an element to the front of the list.

To answer the second half of your question, "Does this hold true for Java also?" The answer is yes, both primitive arrays in Java and ArrayList in Java do not allow prepending to the list without reallocating and moving the elements.

Also, your code is flawed because you are assigning to result and not results, so you aren't actually causing quadratic performance as stated in the question. A better way to demonstrate this behavior would be the following:

results = []
for i in range(1000000):
    results.insert(0, f(i))

And the append version:

results = []
for i in range(1000000):
    results.append(f(i))

Or using the timeit module:

$ python -m timeit 'results = []' 'for i in range(10000): results.insert(0, i)'
10 loops, best of 3: 50.9 msec per loop
$ python -m timeit 'results = []' 'for i in range(10000): results.append(i)'
1000 loops, best of 3: 794 usec per loop

Why does adding to the front of the list take quadratic time?

2 Answers2