Time complexity of python set operations?

by

According to Python wiki: Time complexity, set is implemented as a hash table. So you can expect to lookup/insert/delete in O(1) average. Unless your hash table’s load factor is too high, then you face collisions and O(n).

P.S. for some reason they claim O(n) for delete operation which looks like a mistype.

P.P.S. This is true for CPython, pypy is a different story.

More Related Contents:

  1. Python Sets vs Lists
  2. How is set() implemented?
  3. In Python, when to use a Dictionary, List or Set?
  4. Python dictionary keys. “In” complexity
  5. How do I sort a list of dictionaries by a value of the dictionary?
  6. Converting a list to a set changes element order
  7. Cost of len() function
  8. What would a “frozen dict” be?
  9. How can I create a Set of Sets in Python?
  10. How to convert SQL Query result to PANDAS Data Structure?
  11. How can I extract a single value from a JSON response?
  12. List of all unique characters in a string?
  13. How to construct a set out of list items in python?
  14. Find sets of disjoint sets from a list of tuples or sets in python
  15. How to make a set of lists
  16. What is the difference between sets and lists in Python?
  17. Get unique values in List of Lists
  18. How to implement a binary search tree in Python?
  19. What is time complexity of a list to set conversion?
  20. Fastest way to search a list in python
  21. Understanding the set() function
  22. How to make a dictionary that returns key for keys missing from the dictionary instead of raising KeyError?
  23. What is the runtime complexity of python list functions?
  24. How to create the union of many sets using a generator expression?
  25. Adding counters deletes keys
  26. What is the time complexity of Python list’s count() function?
  27. A set union find algorithm
  28. Python’s and Numpy’s nan and set
  29. performing set operations on custom classes in python
  30. Generate all subsets of size k (containing k elements) in Python

Leave a Comment