Re:Cycle Sort
by eleusive on Monday November 22, 2010 @06:29AM
(#1929436)
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/