Python sets and dictionaries can have quadratic-time performance
Python's dict and set are widely believed to be O(1), but Daniel Lemire shows they can degrade to quadratic time when hash collisions are deliberately induced. On an M4 Max with Python 3.14, inserting 16,000 colliding keys took 1,072 ms, quadrupling as n doubled, and building a set of 100,000 took 45 seconds. Even without collisions, lookups slow from 22 ns to 202 ns per key as a dict grows to a million entries, due to cache misses. The lesson: constant-time hashing is a model, not reality.
The time roughly quadruples each time n doubles. That is quadratic time, not linear time.
- xboxnolifes
Reminds me of the article about random memory access being O(√N): https://www.ilikebigbits.com/2014_04_21_myth_of_ram_1.html
- juancn
That's usually true of all common hash table implementations (when objects don't have a defined order, if they have you can get O(1) average and O(log N) worst case), regardless of language.
The O(1) is the expected average case, which usually holds.
Yeah, O(N^2) is theoretically possible, but unless you're defending against some sort of denial of service attack, in practice it rarely matters.
Still, if you can guess a sensible initial size for a hash table you can avoid a lot of the overhead of rehashing.
- northisup
Raymond Hettinger has a great talk about how much python's dict has improved over the years. So this is super interesting and will probably just make the builtin dict better eventually.
The lesson of the talk is that if you are idiomatic then you will benefit as the language improves.
- ok123456
Most algorithm analyses don't incorporate memory hierarchies. I'm not sure what the point of this post was.
If you are really concerned about it, compute the empirical roofline for your machine.
Also, if the point is to point out memory hierarchies, it's not 'quadratic performance.' The algorithm doesn't behave differently once it spills over. The costs just get bigger.
- brudgers
But could we create a hash table that would be truly constant-time? No. As the size of your data structure grows, it requires progressively slower memory.
At a large enough size to be interesting, everything is dominated by IO and because IO is slow, at any interesting size performance is a matter of tailoring the implementation to the details of the data {0}.
Engineering is hard work, not naive math.
[0] Data might be arbitrary but it is never random. Not being random is what makes it data.