Python collections.Counter: most_common complexity
What is the complexity of the function most_common provided by the collections.Counter object in Python?
More specifically, is Counter keeping some kind of sorted list while it's counting, allowing it to perform the most_common operation faster than O(n) when n 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.
I checked the official documentation and the TimeComplexity article on the CPython wiki but I couldn't find the answer.
Answer
From the source code of collections.py, we see that if we don't specify a number of returned elements, most_common returns a sorted list of the counts. This is an O(n log n) algorithm.
If we use most_common to return k > 1 elements, then we use heapq.nlargest. This is an O(k) + O((n - k) log k) + O(k log k) algorithm, which is very good for a small constant k, since it's essentialy linear. The O(k) part comes from heapifying the initial k counts, the second part from n - k calls to heappushpop method and the third part from sorting the final heap of k elements. Since k <= n we can conclude that the complexity is:
O(n log k)
If k = 1 then it's easy to show that the complexity is:
O(n)