Complexity of list.index(x) in Python


Question

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?

1
24
9/25/2016 9:38:49 PM

Accepted Answer

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

33
9/24/2016 8:10:47 PM

According to said documentation:

list.index(x)

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
Icon