alt Hacker NewsI 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.
Replies
jpitz • yesterday at 6:11 PM
Yeah but there's a formal term for average time complexity, Theta
➕ show 2 replies
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.