What is the time complexity of Python list's count() function?

Question

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?

Solution 1

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.

Solution 2

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

Solution 3

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).

Comments

[SW Williams]

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.

[Bill the Lizard]

@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.

[g.d.d.c]

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).