4 ms·
> 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 compl
by emil-lp 6d ago
> 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.
- robertlagrant 6d agoI 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.
- jpitz 6d agoYeah but there's a formal term for average time complexity, Theta
- emil-lp 6d agoΘ does not usually mean average, but simultaneously upper and lower asymptotic bounds.
- xdavidliu 6d agoyou might want to read that chapter of CLRS again
- jpitz 6d agoYou're right. It isn't the average bound, it is the upper and lower bound stated together ( as long as thats the same function )
- lou1306 6d agoO(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.
- d0mine 4d agoIt 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.
- t-writescode 6d agoPeople … 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.