Python collections.Counter: most_common complexity

by

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)

More Related Contents:

  1. How do I profile a Python script?
  2. How to improve performance of this code?
  3. Find common substring between two strings
  4. How to count the frequency of the elements in an unordered list?
  5. Is the time-complexity of iterative string append actually O(n^2), or O(n)?
  6. Complexity of *in* operator in Python
  7. Time complexity of string slice
  8. Having trouble making a list of lists of a designated size [duplicate]
  9. Time complexity of string concatenation in Python [duplicate]
  10. Pandas groupby.size vs series.value_counts vs collections.Counter with multiple series
  11. Surprising results with Python timeit: Counter() vs defaultdict() vs dict()
  12. Why is Collections.counter so slow?
  13. How to count the number of words in a sentence, ignoring numbers, punctuation and whitespace?
  14. What is time complexity of a list to set conversion?
  15. Why is the time complexity of Python’s list.append() method O(1)?
  16. Creating an Ordered Counter
  17. Sliding window maximum in O(n) time
  18. How to sort Counter by value? – python
  19. Python: Removing Rows on Count condition
  20. How to get count dict of items but maintain the order in which they appear?
  21. Adding counters deletes keys
  22. What is the time complexity of Python list’s count() function?
  23. Finding the most frequent character in a string
  24. Python: is “except KeyError” faster than “if key in dict”?
  25. What is the cost/ complexity of insert in list at some location?
  26. Runtime of python’s if substring in string
  27. Pandas DataFrame search is linear time or constant time?
  28. How to count top 10 most common values in a dict in python
  29. fastest method of getting k smallest numbers in unsorted list of size N in python?
  30. What is the computational complexity of `itertools.combinations` in python?

Leave a Comment