Clash Royale CLAN TAG#URR8PPP

Complexity of *in* operator in Python [closed]

What is the complexity of the in operator in Python? Is it theta(n)?

Is it the same as the following?

def find(L, x)
for e in L:
if e == x:
return True
return False


L is a list.

It's difficult to tell what is being asked here. This question is ambiguous, vague, incomplete, overly broad, or rhetorical and cannot be reasonably answered in its current form. For help clarifying this question so that it can be reopened, visit the help center. If this question can be reworded to fit the rules in the help center, please edit the question.

OMG, it completely depends on what L is.
– Zaur Nasibov
Dec 14 '12 at 18:19

It depends on the type of container, since using it with a dictionary or set will be much faster than with an array.
– Greg Hewgill
Dec 14 '12 at 18:19

@BasicWolf I have used L, so it is list
– Sajjad
Dec 14 '12 at 18:29

@Rastegar L doesn't imply a list. seq is the most common choice where one wants to imply a list. L is a terrible variable name. Single letter ones are bad, and the capital implies it's a class. Even if it was something in particular, Python is dynamic, so state it explicitly in a case like this.
– Gareth Latty
Dec 14 '12 at 18:50

L

seq

L

L means list? My libtelepathy.so is probably outdated.
– Zaur Nasibov
Dec 14 '12 at 18:56

L

list

3 Answers
3

The complexity of in depends entirely on what L is. e in L will become L.__contains__(e).

in

L

e in L

L.__contains__(e)

See this time complexity document for the complexity of several built-in types.

Here is the summary for in:

in

The O(n) worst case for sets and dicts is very uncommon, but it can happen if __hash__ is implemented poorly. This only happens if everything in your set has the same hash value.

__hash__

Why the downvote?
– Andrew Clark
Apr 24 '14 at 18:08

Does anyone happen to know the complexity of the "in" operator for an OrderedDict?
– Josh Sherick
Aug 4 '15 at 19:19

After some testing, I can confirm that the complexity of OrderedDict in Python 2.7 appears to be O(1) in the average case.
– Josh Sherick
Aug 4 '15 at 19:56

It depends entirely on the type of the container. Hashing containers (dict, set) use the hash and are essentially O(1). Typical sequences (list, tuple) are implemented as you guess and are O(n). Trees would be average O(log n). And so on. Each of these types would have an appropriate __contains__ method with its big-O characteristics.

dict

set

list

tuple

__contains__

of value is to include the overhead of generating the hash.
– Woot4Moo
Dec 14 '12 at 18:20

Hashing data types include dict and set (as wells as potentially others)
– Dave
Dec 14 '12 at 18:20

dict

set

@Woot4Moo: When you're talking about asymptotic complexity, that isn't relevant. The overhead of generating the hash is constant. When you're dealing with small values of N, profiling becomes important, because, say, 100 >> 2N for small N. But that's a separate issue from what the OP was asking about; for huge N, 100 << 2N, which is what complexity is all about.
– abarnert
Dec 14 '12 at 19:15

@abarnert well it actually is quite relevant, as you don't arbitrarily choose data structures. You must consider the use and most common ways the structure will be used, so it actually is important to consider the amount of time for a hash function, especially in a scenario where the has must be computed per iteration of a program.
– Woot4Moo
Dec 14 '12 at 19:17

@Woot4Moo: If someone is asking about asymptotic complexity, either (a) they expect to deal with a large N, or (b) they're an idiot. I'm assuming the OP is case (a), but either way, the constant factor isn't relevant to the answer.
– abarnert
Dec 14 '12 at 20:34

It depends on the container you're testing. It's usually what you'd expect - linear for ordered datastructures, constant for the unordered. Of course, there are both types (ordered or unordered) which might be backed by some variant of a tree.

@ZoranPavlovic A in B tests whether A is in B.
– Marcin
Apr 24 '14 at 13:50

A in B

A

B