What is the time complexity of collections.Counter() in Python?

Question

collection.Counter("bcdefffaa")

returns output:

Counter({'f': 3, 'a': 2, 'c': 1, 'b': 1, 'e': 1, 'd': 1})

Since the result is in descended sorted order of values, does this mean the cost of building the Counter is O(nlogn) and not O(n)?

Answer 1

As the source code shows, Counter is just a subclass of dict. Constructing it is O(n), because it has to iterate over the input, but operations on individual elements remain O(1).

Note also from that source that it does not keep an order internally, but simply sorts by most common on output, in the __repr__ method.

Answer 2

Depends on the implementation, obviously, but the factors that matter are the need to touch each element of the original list, which implies O(n) is a lower bound, and the need to insert elements into a dict and/or update a dict. The display of the elements in the output is not relevant to the cost of building the Counter.