What is the runtime complexity of python list functions?

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)

Lists are indeed O(1) to index - they are implemented as a vector with proportional overallocation, so perform much as you'd expect. The likely reason you were finding this code slower than you expected is the call to "range(0, len(some_list))".

range() creates a new list of the specified size, so if some_list has 1,000,000 items, you will create a new million item list up front. This behaviour changes in python3 (range is an iterator), to which the python2 equivalent is xrange, or even better for your case, enumerate

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)

if you need index and value then use enumerate:

for idx, item in enumerate(range(10, 100, 10)):
    print idx, item