Hacker News Reader

> To put it differently, saying that a hash table is O(1) or constant time is a model

Nobody really says that, nor is it a model. It is the expected time complexity.

People … say that all the time. *I* say that all the time. It’s true enough to be accurate in 99.9% of the cases; and we put barriers in place when implementing code (like configuring the hashing algorithm) to keep it that way.

I think people do say a hash table is O(1). It's the average time complexity (for some value of average) though, not the worst case.

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

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

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 )

O(1) insertion is the amortized worst-case time complexity, actually. (Amortized in the sense that the O(n) cost of copying is paid only during the n-th insertion). Average complexity is a slightly different thing.

It is not “worst-case” (as the post demonstrates, you can get worse results by using specifically crafted data that exploits hash collisions). There are algorithms that can get you O(logN) instead of O(N) even on such data.

Reply on news.ycombinator.com