The runtime complexity of the len() function on your Python list is O(1). It takes constant runtime no matter how many elements are in the list. Why? Because the list object maintains an integer counter that increases and decreases as you add and remove list elements. Looking up the value of this counter takes constant time.
Python list objects keep track of their own length. When you call the function len(...) on a list object, here’s what happens (roughly):
- The Python virtual machine looks up the
len(...)function in a dictionary to find the associated implementation. - You pass a list object as an argument to the
len()function so the Python virtual machine checks the__len__method of the list object. - The method is implemented in C++ and it’s just a counter that’s increased each time you add an element to the list and decreased if you remove an element from the list. For example, say, the variable
lengthstores the current length of the list. The method then returns the valueself.length. - Done.
Here’s a snippet of the C++ implementation of the list data structure:
static int
list_resize(PyListObject *self, Py_ssize_t newsize)
{
PyObject **items;
size_t new_allocated, num_allocated_bytes;
Py_ssize_t allocated = self->allocated;
// some implementation details
Py_SET_SIZE(self, newsize);
self->allocated = new_allocated;
return 0;
}What’s the Runtime Complexity of Other Python List Methods?
Here’s the table based on the official Python wiki:
| Operation | Average Case | Amortized Worst Case |
| copy() | O(n) | O(n) |
| append() | O(1) | O(1) |
| pop() | O(1) | O(1) |
| pop(i) | O(k) | O(k) |
| insert() | O(n) | O(n) |
| list[i] | O(1) | O(1) |
| list[i] = x | O(1) | O(1) |
| remove(x) | O(n) | O(n) |
| for i in list | O(n) | O(n) |
| list[i:j] | O(k) | O(k) |
| del list[i:j] | O(n) | O(n) |
| list[i:j] = y | O(k+n) | O(k+n) |
| extend() | O(k) | O(k) |
| sort() | O(n log n) | O(n log n) |
| […] * 10 | O(nk) | O(nk) |
x in lst | O(n) | |
| min(lst), max(lst) | O(n) | |
| len(lst) | O(1) | O(1) |
The Python list is implemented using a C++ array. This means that it’s generally slow to modify elements at the beginning of each list because all elements have to be shifted to the right. If you add an element to the end of a list, it’s usually fast. However, resizing an array can become slow from time to time if more memory has to be allocated for the array.
Related articles:
Where to Go From Here
If you keep struggling with those basic Python commands and you feel stuck in your learning progress, I’ve got something for you: Python One-Liners (Amazon Link).
In the book, I’ll give you a thorough overview of critical computer science topics such as machine learning, regular expression, data science, NumPy, and Python basics—all in a single line of Python code!
OFFICIAL BOOK DESCRIPTION: Python One-Liners will show readers how to perform useful tasks with one line of Python code. Following a brief Python refresher, the book covers essential advanced topics like slicing, list comprehension, broadcasting, lambda functions, algorithms, regular expressions, neural networks, logistic regression and more. Each of the 50 book sections introduces a problem to solve, walks the reader through the skills necessary to solve that problem, then provides a concise one-liner Python solution with a detailed explanation.