19

I'm trying to figure what the time complexity of the count() function.

Ex if there is a list of [1, 2, 2, 3] and [1, 2, 2, 3].count(2) is used.

I've searched endlessly and looked at the Python wiki here, but its not there.

The closest I've come to finding an answer is here, but the field for complexity happens to be empty... Does anyone what the answer is?

iehrlich
  • 3,572
  • 4
  • 34
  • 43
SW Williams
  • 559
  • 1
  • 5
  • 18
  • 1
    Well, to count the number of elements of a list, there is no way round checking all the elements. That means we will end up at O(n). – JohanL Jun 28 '17 at 21:03
  • try it yourself.. construct lists using range() of ever increasing size and time the `count` function. Is it linear? – Ma0 Jun 28 '17 at 21:03
  • 1
    You'll find that most documentation is pretty terrible about giving asymptotic complexities for things. The only place I've seen consistent availability of time complexity information is the C++ standard library. – user2357112 Jun 28 '17 at 21:09
  • "Well, to count the number of elements of a list, there is no way round checking all the elements." I could make an list implementation where count is O(1) by keeping track of the occurrences and increment when the same value is appended. Just didn't want to make any assumption about Python's implementation. – SW Williams Jun 28 '17 at 21:23
  • Possible duplicate of [How to find time complexity of an algorithm](https://stackoverflow.com/questions/11032015/how-to-find-time-complexity-of-an-algorithm) – GIZ Jun 28 '17 at 21:35

3 Answers3

32

Dig into the CPython source code and visit Objects/listobject.c, you will find the source code for the count() method in there. It looks like this:

static PyObject *
list_count(PyListObject *self, PyObject *value)
{
    Py_ssize_t count = 0;
    Py_ssize_t i;

    for (i = 0; i < Py_SIZE(self); i++) {
        int cmp = PyObject_RichCompareBool(self->ob_item[i], value, Py_EQ);
        if (cmp > 0)
            count++;
        else if (cmp < 0)
            return NULL;
    }
    return PyLong_FromSsize_t(count);
}

What it does is to simply iterate over every PyObject in the list, and if they are equal in rich comparision (see PEP 207), a counter is incremented. The function simply returns this counter.

In the end, the time complexity of list_count is O(n). Just make sure that your objects don't have __eq__ functions with large time complexities and you'll be safe.

Berk Özbalcı
  • 3,016
  • 3
  • 21
  • 27
6

Because the count method has to check every entry in the list, the runtime is going to be O(n).

g.d.d.c
  • 46,865
  • 9
  • 101
  • 111
  • 3
    But that's assuming the implementation. From what I learned in class Python has quite a few implementation that are faster than expected. For example count can be O(1) if we keep track of the number of occurrences when an item is appended. Just didn't want to make any assumptions. – SW Williams Jun 28 '17 at 21:21
  • @SWWilliams That would work for a length function, where you're just interested in how many items are in the list, but it would be inefficient to store the count of each piece of data in a list. – Bill the Lizard Jun 28 '17 at 21:25
  • There are other classes in python (ie Counter) that keep track of elements differently and can provide answers like this without taking O(n) time. They do so at the cost of memory overhead (something which may or may not be critical in your application). But for the question as asked, the time for `list.count()` is O(n). – g.d.d.c Jun 28 '17 at 22:29
2

It needs needs to visit all elements in order to know whether to count them or not. There is no reason for it to do any more work than that.

So, it cannot possibly be better than O(n), and since even the most basic, simple, straightforward implementation is O(n), you would need to actually be either very stupid or very malicious to make it any slower.

Ergo, by common sense, the worst-case step complexity is most likely O(n).

Jörg W Mittag
  • 363,080
  • 75
  • 446
  • 653