Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Python sets and dictionaries can have quadratic-time performance

lemire.me

Post reply on HN
Print view View original

31–40 of 67 posts

Re: Python sets and dictionaries can have quadratic-time performance

#31

Post by ot »

O(1) doesn't mean constant, it means bounded by a constant. An algorithm can be faster with small n and converge to a horizontal asymptote as n goes to infinity, and it would still be O(1).

In a real machine there is no infinity, but hundreds of GBs of memory are "infinity enough" compared to the cache size [1]. So asymptotic analysis is still a decent model.

I'm surprised that even a CS professor confuses this.

[1] Ok if we want to be pedantic memory access is logarithmic due to the traversal of page tables, but you can use huge pages.

Re: Python sets and dictionaries can have quadratic-time performance

#32

Post by jpitz »

xdavidliu wrote: post #24
jpitz wrote: post #18

Earlier quoted context omitted.

Yeah but there's a formal term for average time complexity, Theta

you might want to read that chapter of CLRS again

You're right.

It isn't the average bound, it is the upper and lower bound stated together ( as long as thats the same function )

Re: Python sets and dictionaries can have quadratic-time performance

#33

Post by taeric »

juancn wrote: post #9

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…

I used to think of it more as O(1) being the expected average of the cases. My guess is I'm probably thinking of it more as an amortized cost, in that framing? (That is, not that it is the average case. Is the average of all cases.)

To your point on the worst case being something you may worry about in denial of service, I think it is often the case that people should set bounds on what size N they will deal with in a program. And then decide from there on whether you are worried about some of the more esoteric growth patterns.

Re: Python sets and dictionaries can have quadratic-time performance

#34

Post by koala_man »

ok123456 wrote: post #28

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.

> The costs just get bigger.

By a constant factor no less (until we get into theoretical physics)

Re: Python sets and dictionaries can have quadratic-time performance

#36

Post by streetfighter64 »

brudgers wrote: post #5

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…

> Data might be arbitrary but it is never random. Not being random is what makes it data.

Counterexamples: crypto keys, stock price history, weather observations, radio telescope recordings

Re: Python sets and dictionaries can have quadratic-time performance

#37

Post by Drupon »

Real big brain moment in the comments

>Can we say that since every real-life data structure size is bounded by some constant, it is O(1)? If not, why?

>>You may, yes.

Very powerful thinking coming from someone who is "a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers"

Re: Python sets and dictionaries can have quadratic-time performance

#38

Post by anewhnaccount2 »

Drupon wrote: post #37

Real big brain moment in the comments >Can we say that since every real-life data structure size is bounded by some constant, it is O(1)? If not, why? >>You may, yes. Very powerful thinking coming from someone who is "a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers"

It's true you can. Just as you can say that you can enumerate all memory states in a real computer so it can be modelled as a finite state machine. These asymptotic models aren't real (our world as we experience it is finite and bounded) and exist as models from which to gain insights which we can transfer back. I love this argument BTW a classic that usually comes up in these discussions.

Re: Python sets and dictionaries can have quadratic-time performance

#39

Post by lenerdenator »

Drupon wrote: post #37

Real big brain moment in the comments >Can we say that since every real-life data structure size is bounded by some constant, it is O(1)? If not, why? >>You may, yes. Very powerful thinking coming from someone who is "a software performance expert. He ranks among the top 2% of scientists globally (Stanford/Elsevier 2025) and is one of GitHub's top 1000 most followed developers"

> Stanford

Mmmmm. Yep. There's yer trouble.

Re: Python sets and dictionaries can have quadratic-time performance

#40

Post by afdbcreid »

taeric wrote: post #33
juancn wrote: post #9

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…

I used to think of it more as O(1) being the expected average of the cases. My guess is I'm probably thinking of it more as an amortized cost, in that framing? (That is, not that it is the average case. Is the average of all cases.) To your point on the worst case being something you may worry about in denial of service, I think it is often the case that people should set bounds on what size N they will deal with in…

It is both amortized and average, because the map may need to grow. But the complexity without growing is average, not amortized (it's possible to build hash functions for which the probability will mean O(1) for all accesses, and hash functions which will be O(N) for all accesses).
Post reply on HN