title: Python complexity reference?
body: <p>Is there any Python complexity reference? In <a href="http://en.cppreference.com/w/">cppreference</a>, for example, for many functions (such as <a href="http://en.cppreference.com/w/cpp/container/array/size">std::array::size</a> or <a href="http://en.cppreference.com/w/cpp/container/array/fill">std::array::fill</a>) there's a <strong>complexity</strong> section which describes their running complexity, in terms of <em>linear in the size of the container</em> or <em>constant</em>.</p>
  
  <p>I would expect the same information to appear in the python website, perhaps, at least for the CPython implementation. For example, in the <a href="http://docs.python.org/2/tutorial/datastructures.html#more-on-lists">list reference</a>, in <code>list.insert</code> I would expect to see <strong>complexity: linear</strong>; I know this case (and many other container-related operations) is covered <a href="https://wiki.python.org/moin/TimeComplexity">here</a>, but many other cases are not. Here are a few examples:</p>
  
  <ul>
  <li>What is the complexity of <code>tuple.__le__</code>? It seems like when comparing two tuples of size <code>n</code>, <code>k</code>, the complexity is about <code>O(min(n,k))</code> (however, for small <code>n</code>'s it looks different).</li>
  <li>What is the complexity of <a href="http://docs.python.org/2/library/random.html#random.shuffle"><code>random.shuffle</code></a>? It appears to be <code>O(n)</code>. It also appears that the complexity of <a href="http://docs.python.org/2/library/random.html#random.randint"><code>random.randint</code></a> is <code>O(1)</code>.</li>
  <li>What is the complexity of the <code>__format__</code> method of strings? It appears to be linear in the size of the input string; however, it also grows when the number of <strong>relevant</strong> arguments grow (compare <code>("{0}"*100000).format(*(("abc",)*100000))</code> with <code>("{}"*100000).format(*(("abc",)*100000))</code>).</li>
  </ul>
  
  <p>I'm aware that (a) each of these questions may be answered by itself, (b) one may look at the code of these modules (even though some are written in C), and (c) StackExchange is not a python mailing list for user requests. So: this is not a doc-feature request, just a question of two parts:</p>
  
  <ol>
  <li>Do you know if such a resource exists?</li>
  <li>If not, do you know what is the place to ask for such, or can you suggest why I don't need such?</li>
  </ol>