Complexity of list.index(x) in Python
Solution 1
It's O(n), also check out: http://wiki.python.org/moin/TimeComplexity
This page documents the time-complexity (aka "Big O" or "Big Oh") of various operations in current CPython. Other Python implementations (or older or still-under development versions of CPython) may have slightly different performance characteristics. However, it is generally safe to assume that they are not slower by more than a factor of O(log n)...
Solution 2
Any list implementation is going to have an O(n) complexity for a linear search (e.g., list.index). Although maybe there are some wacky implementations out there that do worse...
You can improve lookup complexity by using different data structures, such as ordered lists or sets. These are usually implemented with binary trees. However, these data structures put constraints on the elements they contain. In the case of a binary tree, the elements need to be orderable, but the lookup cost goes down to O(log n).
As mentioned previously, look here for run time costs of standard Python data structures: http://wiki.python.org/moin/TimeComplexity
user734027
Updated on July 09, 2022Comments
-
user734027 almost 2 years
I'm referring to this: http://docs.python.org/tutorial/datastructures.html
What would be the running time of
list.index(x)
function in terms of Big O notation?