CODEWITHSUNDEEP
pythonstringlisttime-complexityin-operator
Lindsey
Lindsey

Reputation: 13

Is there a difference in time complexity of the "in" operator for strings compared to lists?

I was wondering if there is any benefit to searching for a string in a list compared to searching for a substring in a string using the "in" operator.

I have always checked for a substring using the following:

substr in str

But I came across a piece of code that split the string and then performed the check.

substr in str.split()

Is there any benefit performance-wise or other, or was this just a preference for that programmer.

Thanks!

Upvotes: 1

Views: 179

Answers (2)

Demi-Lune
Demi-Lune

Reputation: 1977

As already mentioned, it can be slightly different:

>>> "Python" in "Monty Python's Flying Circus"
True
>>> "Python" in "Monty Python's Flying Circus".split()
False

And from a performance point of view, split is a lot more expensive (it creates a temporary list):

>>> from timeit import timeit
>>> timeit("""'Monty' in "Monty Python's Flying Circus".split() """)
0.20677191999857314
>>> timeit("""'Monty' in "Monty Python's Flying Circus" """)
0.03346360499563161

We could also probably argue that if the word you're looking for is near the beginning of the sentence, the sub in str will be a best case scenario in O(1) (the in operation is probably coded with C's strstr); while the sub in str.split() will still have to split the whole text before starting to look for the word (so best-case scenario is always at least O(n), more memory consuming, etc.).

Upvotes: 1

chepner
chepner

Reputation: 531235

Those do two different things. The complexity of both is O(n), but that's not really relevant because you wouldn't choose one over the other for how fast they are; you'd make the choice based on what you actually want to do.

>>> "o b" in "foo bar"  # "o b" is a substring of "foo bar"
True
>>> "o b" in "foo bar".split()  # "o b" is not an element of ["foo", "bar"]
False

Upvotes: 4

Related Questions