What is the secret behind Python's len() builtin time complexity of O(1)

user_10172812 0
Viewed 4242

Since Python is implemented in C, I am confused how the developers managed to make the Python builtin len function run on any sequence in constant time, O(1), while C's string function strlen runs in linear time, O(n).

What is the secret behind Python's builtin len functions's time complexity? If we were to write program in C, would it be best practice to copy Python's code for len if we ever wanted to a fast C program involves sequence length?

time-complexity c python
2 Answers

I guess you are missing one concept that is how a data structure can return its size in constant time i.e. O(1).

Roughly, think of a program like this:

void init(){
     // code to initialize (or allocate memory) the container 
     size = 0;
}
void add(Something something){
     container.add(something);
     size++;
}
void remove(Something something){
   //Code to search 'something'
   if(found) { 
    container.remove(something); 
    size--;
   }
}
int len(){
    return size;
}

Now any time you call the method len(), it is ready to return the integral value without any need to traverse the container.

Why strlen or any C related data structure doesn't work that way is because of the space overhead of having a counter like size. But that doesn't mean you can't define one. Hint: Use struct and keep the size maintained there.

user_14655530

Any string/list in python is an object. Like many objects, it has a __len__ method, which stores the length of the list. When we call len, __len__ gets called internally, and returns the stored value, which is an O(1) operation.

user_50191690
Related