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?
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)...
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
False you're returning the index of
x. As such, I'd go with the listed time complexity of O(n).