What is the runtime complexity of python list functions?

Question

I was writing a python function that looked something like this

def foo(some_list):    for i in range(0, len(some_list)):        bar(some_list[i], i) 

so that it was called with

x = [0, 1, 2, 3, ... ] foo(x) 

I had assumed that index access of lists was O(1), but was surprised to find that for large lists this was significantly slower than I expected.

My question, then, is how are python lists are implemented, and what is the runtime complexity of the following

• Indexing: list[x]
• Popping from the end: list.pop()
• Popping from the beginning: list.pop(0)
• Extending the list: list.append(x)

For extra credit, splicing or arbitrary pops.

Answer 1

there is a very detailed table on python wiki which answers your question.

However, in your particular example you should use enumerate to get an index of an iterable within a loop. like so:

for i, item in enumerate(some_seq):     bar(item, i) 

Answer 2

The answer is "undefined". The Python language doesn't define the underlying implementation. Here are some links to a mailing list thread you might be interested in.

• It is true that Python's lists have been implemented as contiguous vectors in the C implementations of Python so far.

• I'm not saying that the O() behaviours of these things should be kept a secret or anything. But you need to interpret them in the context of how Python works generally.

Also, the more Pythonic way of writing your loop would be this:

def foo(some_list):    for item in some_list:        bar(item)