title: Python collections.Counter: most_common complexity
body: <p>What is the complexity of the function <code>most_common</code> provided by the <code>collections.Counter</code> object in Python?</p>
  
  <p>More specifically, is <code>Counter</code> keeping some kind of sorted list while it's counting, allowing it to perform the <code>most_common</code> operation faster than <code>O(n)</code> when <code>n</code> is the number of (unique) items added to the counter? For you information, I am processing some large amount of text data trying to find the n-th most frequent tokens.</p>
  
  <p>I checked the <a href="https://docs.python.org/library/collections.html#collections.Counter" rel="noreferrer">official documentation</a> and the <a href="https://wiki.python.org/moin/TimeComplexity" rel="noreferrer">TimeComplexity article</a> on the CPython wiki but I couldn't find the answer.</p>