Time complexity of list.count in Python

Question

Recently, I've came across this article on Microsoft documentation:
http://msdn.microsoft.com/en-us/library/27b47ht3%28v=vs.110%29.aspx
It's about the implementation of list.count in C#, from what I can see, it uses an internal int to track the number of items, so retrieving count is O(1) operation.

count can definitely reduce some lines and can be pretty helpful some times, but I always try to avoid it in algorithms, because I thought it iterated over the whole list, so using it in the loop makes the time complexity of the algorithm O(N^2) which is not optimal.

Unfortunately I couldn't find anything similar to this for python, I can't understand C well, so I couldn't analyze the implementation from the source code, could anyone explain how is it implemented? What is the time complexity?

Answer 1

Bagon I've done some research in the CPython code and found that ob_size is no longer part of the PyListObject struct so it has to iterate over the list to count the elements. This means that at least CPython has O(n) for counting list elements. Other implementations however might handle this differently.

Answer 2

Aaron Eberhardt alright thanks for the time, appreciate it

Answer 3

I think the count function is O(1) because the element count is updated every time elements are added or removed. Rather than iterating over the list the function just needs to retrieve a attribute of the List object.

The Python implementation of the List object is internally stored in a struct that has a ob_size element so it's likely Python does handle this like C#. But of course Python will still be much slower than C# (even though C# isn't the fastest language either).
If you want to speed up your Python you could have a look at this project that sound pretty promising: https://pyo3.rs/v0.11.1

Answer 4

Aaron Eberhardt thanks, understood. Speeding it up isn't really what I'm aiming for but will check it out

Answer 5

Bagon
Time complexity is O(n) according to this answer (at least for CPython).
https://stackoverflow.com/a/44813154

Answer 6

AKSHAY I want to know how the list.count method is implemented in python (how does it work/time complexity)

Answer 7

AKSHAY yeah it takes one value as an argument and then returns how many times has that value been found in the list

Answer 8

Bagon yes it also works in python

https://code.sololearn.com/cTvqMk2J67ib/?ref=app

Answer 9

AKSHAY yeah I know it's implemented in python and that's why I wanted to know more about it

Answer 10

Martin LOOTER King yes that seems like O(n), tho the source is a bit different, might be changed?..

Answer 11

Bagon what do you want to actually do, can you please more clarify it in short.
Do you want to count the number of items in list??

Answer 12

Bagon if so you can use "len(list)" to get the number of items in a list

Answer 13

Bagon does list.count method counts the number of items in list ??
(As I am not fond C#)