CODEWITHSUNDEEP
pythonlistdictionarytime-complexity
Cisac
Cisac

Reputation: 71

Time Complexity of "in" (containment operator)

I was just wondering when understanding the time complexity of an algorithm like the one below.

For a python list, if we have a for loop iterating over it, and then a containment check, would the time complexity of that be O(n^2).

I know both are O(n) (or I think) so having them nested in one another would that make it O(n^2)?

I think if this "list" is actually a list, then the time complexity of the code below is O(n^2). But if it's a dictionary it would be O(n) because lookup is O(1). Is that correct?

Thanks for any help in advance!

for element in list:
    if x in list:

Upvotes: 6

Views: 2823

Answers (1)

John Kugelman
John Kugelman

Reputation: 361645

Your analysis is correct.

  • List containment is O(n), and doing an O(n) operation O(n) times is O(n2).
  • Dictionary lookups are O(1), and doing an O(1) operation O(n) times is O(n).

Upvotes: 4

Related Questions