title: What is the runtime complexity of python list functions?
body: <p>I was writing a python function that looked something like this</p>
  
  <pre><code>def foo(some_list):
     for i in range(0, len(some_list)):
         bar(some_list[i], i)
  </code></pre>
  
  <p>so that it was called with</p>
  
  <pre><code>x = [0, 1, 2, 3, ... ]
  foo(x)
  </code></pre>
  
  <p>I had assumed that index access of lists was <code>O(1)</code>, but was surprised to find that for large lists this was significantly slower than I expected.</p>
  
  <p>My question, then, is how are python lists are implemented, and what is the runtime complexity of the following</p>
  
  <ul>
  <li>Indexing: <code>list[x]</code></li>
  <li>Popping from the end: <code>list.pop()</code></li>
  <li>Popping from the beginning: <code>list.pop(0)</code></li>
  <li>Extending the list: <code>list.append(x)</code></li>
  </ul>
  
  <p>For extra credit, splicing or arbitrary pops.</p>