Complexity of list.index(x) in Python


I'm referring to this:

What would be the running time of list.index(x) function in terms of big O notation?

9/25/2016 9:38:49 PM

Accepted Answer

It's O(n), also check out:

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)...

9/24/2016 8:10:47 PM

According to said documentation:


Return the index in the list of the first item whose value is x. It is an error if there is no such item.

Which implies searching. You're effectively doing x in s but rather than returning True or False you're returning the index of x. As such, I'd go with the listed time complexity of O(n).

Licensed under: CC-BY-SA with attribution
Not affiliated with: Stack Overflow