Python Str.index Time Complexity

For finding the position of a substring, inside a string, a naive algorithm will take O(n^2) time. However, using some efficient algorithms (eg KMP algorithm), this can be achieved

Solution 1:

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 inorderto 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 stringis 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

Solution 2:

its a combination of a few algorithms- look at this

Python string 'in' operator implementation algorithm and time complexity

or this

http://effbot.org/zone/stringlib.htm

Solution 3:

Sometimes you can get a quick answer just by trying

>>> timeit.timeit('x.index("ra")', setup='x="a"*100+"ra"')
0.4658635418727499
>>> timeit.timeit('x.index("ra")', setup='x="a"*200+"ra"')
0.7199222409243475
>>> timeit.timeit('x.index("ra")', setup='x="a"*300+"ra"')
0.9555441829046458
>>> timeit.timeit('x.index("ra")', setup='x="a"*400+"ra"')
1.1994099491303132
>>> timeit.timeit('x.index("ra")', setup='x="a"*500+"ra"')
1.4850994427915793