Skip to main content
The not in operator is a logical membership operator that evaluates to True if a specified element is absent from a given iterable or sequence, and False if the element is present. It functions as the exact boolean negation of the in operator.

​
Underlying Mechanics

When the Python interpreter evaluates x not in y, it primarily attempts to delegate the operation to the right-hand operand’s __contains__() dunder (magic) method, subsequently applying a logical not to the result.

​
Fallback Resolution

If the target object y does not implement the __contains__() method, Python attempts to resolve the not in expression by falling back to sequential iteration.
  1. The interpreter looks for the __iter__() method to traverse the object.
  2. If __iter__() is missing, it falls back to the old-style sequence protocol using __getitem__(), starting from index 0.
  3. During traversal, Python evaluates x is item or x == item to compare x against each yielded item. Checking identity (is) before equality (==) is a critical semantic optimization. It ensures that objects like float('nan') can be accurately identified in collections, even though nan == nan evaluates to False.
Short-Circuit Evaluation: If the fallback iteration encounters an item where x is item or x == item evaluates to True, the traversal short-circuits immediately, and the not in expression returns False. If the iterable is completely exhausted without a match, it returns True.

​
Algorithmic Complexity

The performance characteristics of the not in operator are strictly dictated by the underlying data structure of the right-hand operand:
  • Hash-based collections (set, dict): The average-case time complexity is O(1). The operator computes the hash of the left-hand operand and performs a direct hash table lookup. Note that for dictionaries, not in evaluates the presence of keys, not values.
  • Sequence collections (list, tuple): The average and worst-case time complexity is O(n). Because these structures lack hashing for their elements, the interpreter must perform a linear scan, comparing the target element against each item sequentially.
  • Strings (str): When both operands are strings, not in performs a substring search rather than a strict character-by-character iteration. It evaluates to False if the left-hand string is a contiguous substring of the right-hand string. The underlying implementation uses fast string-matching algorithms (like Boyer-Moore-Horspool), though worst-case complexity remains O(n * m).
Tired of Poor Python Skills? Fix That With Deep Grasping!Learn More