CODEWITHSUNDEEP
pythontimesizein-operator
Anshu Dwibhashi
Anshu Dwibhashi

Reputation: 4675

Python "in" operator speed

Is the in operator's speed in python proportional to the length of the iterable?

So,

len(x) #10
if(a in x): #lets say this takes time A
    pass

len(y) #10000
if(a in y): #lets say this takes time B
    pass

Is A > B?

Upvotes: 13

Views: 16660

Answers (3)

Freddy Mcloughlan
Freddy Mcloughlan

Reputation: 4506

Assuming x and y are lists:

Is the in operator's speed in Python proportional to the length of the iterable?

Yes.

The time for in to run on a list of length n is O(n). It should be noted that it is O(1) for x in set and x in dict as they are hashed, and in is constant time.

Is A > B?

No.

Time A < Time B as 10 < 10000

Docs: https://wiki.python.org/moin/TimeComplexity

Upvotes: 0

Tim Peters
Tim Peters

Reputation: 70602

There's no general answer to this: it depends on the types of a and especially of b. If, for example, b is a list, then yes, in takes worst-case time O(len(b)). But if, for example, b is a dict or a set, then in takes expected-case time O(1) (i.e., constant time).

About "Is A > B?", you didn't define A or B. As above, there's no general answer to which of your in statements will run faster.

Upvotes: 8

lennon310
lennon310

Reputation: 12689

A summary for in:

list - Average: O(n)
set/dict - Average: O(1), Worst: O(n)

See this for more details.

Upvotes: 38

Related Questions