Python sets and dictionaries can have quadratic-time performance

Which statement in this article applies only to Python?

This "quadratic-time performance" is incredibly disingenuous. First, it's doing n operations that are each O(n), so it's more like "can have linear time performance, but done n times so I can give you a scary title".

Edit: A charitable take is constructing a set/dict from a list is indeed a common operation so it's worthwhile to think about its complexity, but it's not really one of the standard operations when discussing the performance of a hashset/hashmap, so really shouldn't be this handwavy.

And instead of attacking some straw man "It is indeed widely believed that ..." claim (widely believed by who?), why not attack what's literally on docs.python.org? https://docs.python.org/3/library/time-complexity.html:

> dict

> The times listed for dict objects are average-case times, as they assume the hash function for the objects is sufficiently robust to make collisions uncommon. They also assume the keys are well-distributed among the set of possible keys. In the worst case, when every key hashes to the same value, each of the O(1) operations below instead takes O(n) time. They also assume that hashing and comparing a key is O(1). For more detail on the implementation, see How are dictionaries implemented in CPython?.

> ...

> set, frozenset

> See dict as the set and frozenset implementations are similar, and the same caveats apply. In the worst case, O(1) operations instead take O(n) time, and operations that look up every element degrade accordingly.

  +--------------------------------------+------------+
  | Operation                            | Complexity |
  +--------------------------------------+------------+
  | x in s                               | O(1)       |
  | Copy (s.copy()) [6] [7]              | O(n)       |
  | Add (s.add(x)) [1]                   | O(1)       |
  | Discard (s.discard(x), s.remove(x))  | O(1)       |
  | ...                                  | ...        |
  +--------------------------------------+------------+

You explicitly construct a list of ints that are all multiples of sys.hash_info.modulus and hence all hash to 0, no shit you get that well documented O(n) behavior.

The discussion of CPU cache is good though, so why hide that behind this clickbait.

Time complexity is something that applies to algorithms, and is determined analytically. I don't think it's useful to equivocate the definition with performance of implementations of algorithms determined through real world data. Both of these things are important, but they are not the same. The fact that they differ is not very surprising and does not necessarily mean that a misunderstanding has occurred.

Uh, what is going on with this benchmark?

Why is M so big? Why does it cross the maxint boundary? Why is constructing the list comprehension part of the benchmark? Why are we summing the set? Why are we only measuring 5 values for n?

Θ does not usually mean average, but simultaneously upper and lower asymptotic bounds.