python str.index time complexity

Question

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 in O(n) time:

s = 'saurabh'
w = 'au'

def get_table():
    i = 0; j = 2 
    t = []
    t.append(-1); t.append(0)
    while i < len(w):
        if w[i] == w[j-1]:
            t.append(j+1)
            j += 1
        else:
            t.append(0)
            j = 0 
        i += 1
    return t

def get_word():
    t = get_table()
    i = j = 0 
    while i+j < len(s):
        if w[j] == s[i+j]:
            if j == len(w) - 1:
                return i
            j += 1
        else:
            if t[j] > -1: 
                i = i + j - t[j]
                j = t[j]
            else:
                i += 1
    return -1

if __name__ == '__main__':
    print get_word()

However, if we do: 'saurabh'.index('ra'), does it internally uses some efficient algorithm to compute this in O(n) or it uses naive algorithm of complexity O(n^2) ?

You could profile it and see if the time grows exponentially or linearly ;) — Joel Cornett, Apr 26 '16 at 14:52

score 4 · Answer 1 · answered Apr 26 '16 at 15:07

4

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

answered Apr 26 '16 at 15:07

alpert

4,500
1
17
27

But KMP's worst case time is still linear. Does this mean we should implement our code using KMP algorithm instead of python's builtin index() for time critical processes ? – Saurabh Verma Apr 26 '16 at 15:11
I think that thread has a good answer about that topic: http://programmers.stackexchange.com/questions/183725/which-string-search-algorithm-is-actually-the-fastest – alpert Apr 26 '16 at 15:25

score 0 · Answer 2 · edited May 23 '17 at 11:53

0

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

edited May 23 '17 at 11:53

Community

1
1

answered Apr 26 '16 at 15:03

Jonathan

486
3
12

score -1 · Answer 3 · answered Apr 26 '16 at 19:26

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

python str.index time complexity

3 Answers3

Linked