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

Time complexity is O(n) . Have a look at the link

http://wiki.python.org/moin/TimeComplexity

In that article [1] author goes through the algoritm and explains it. From article:

The function “fastsearch” is called. It is a mix between 
Boyer-Moore and Horspool algorithms plus couple of neat tricks.

And from the wiki page of Boyer–Moore–Horspool algorithm [2]:

The algorithm trades space for time in order to obtain an 
average-case complexity of O(N) on random text, although 
it has O(MN) in the worst case, where the length of the 
pattern is M and the length of the search string is N.

Hope that helps!

[1] http://www.laurentluce.com/posts/python-string-objects-implementation

[2] https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore%E2%80%93Horspool_algorithm

Both str.find and str.index are just thin wrappers around any_find_slice, and their only meaningful difference is the addition of the following in str.index:

if (result < 0) {
    PyErr_SetString(PyExc_ValueError, "substring not found");
    return NULL;
}

Thus any perceived runtime differences if true (you haven't included a benchmark that shows your claims are true) must come from the exception handling.