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

by

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.

More Related Contents:

  1. What is the computational complexity of `itertools.combinations` in python?
  2. Removing Capitalized Strings from Input File in Python3.4?
  3. Python – concatenate NoneType and string in a new list
  4. Python evaluates the program without error, sum and average are correct but the product is always the same
  5. Import error: No module name urllib2
  6. What’s the correct way to convert bytes to a hex string in Python 3?
  7. Python webbrowser.open() to open Chrome browser
  8. Beautiful Soup findAll doesn’t find them all
  9. Time complexity of string slice
  10. What is __pycache__?
  11. If range() is a generator in Python 3.3, why can I not call next() on a range?
  12. Why does map return a map object instead of a list in Python 3?
  13. networkx – change color/width according to edge attributes – inconsistent result
  14. What is the purpose of collections.ChainMap?
  15. Why is the purpose of the “else” clause following a “for” or “while” loop? [duplicate]
  16. Python 3: How to specify stdin encoding
  17. Adding a data file in Pyinstaller using the onefile option
  18. Subtract a value from every number in a list in Python?
  19. How does a for loop evaluate its argument
  20. Priority of the logical operators (order of operations) for NOT, AND, OR in Python
  21. How to check if an object has an attribute in Python?
  22. Repeated MySQL queries from Python return the same data [duplicate]
  23. @classmethod vs @staticmethod in Python
  24. Error while downloading the requirements using pip install (setup command: use_2to3 is invalid.)
  25. What does it mean when the parentheses are omitted from a function or method call?
  26. How to implement barriers to stop the player moving through walls
  27. Disable hash randomization from within python program
  28. nargs=* equivalent for options in Click
  29. Set encoding in Python 3 CGI scripts
  30. Static variable in Python?

Leave a Comment