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)
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.
Also, the more Pythonic way of writing your loop would be this:
def foo(some_list):
for item in some_list:
bar(item)
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