What is the runtime complexity of python list functions?
complexity-theory, python
Solution
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)
Problem
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.