In particular, a good hash table implementation will have O(1) amortized complexity [1] (i.e. average complexity over a worst-case sequence of operations). Sin

In particular, a good hash table implementation will have O(1) amortized complexity [1] (i.e. average complexity over a worst-case sequence of operations). Since in the Real World we deal with sequences of operations rather than single ones, saying that hash tables provide O(1) operations is quite correct. [1] http://videolectures.net/mit6046jf05_leiserson_lec13/ http://videolectures.net/mit6046jf05_leiserson_lec13/