Gaming CS Interviews
The conflation of &quot;amortized&quot; with &quot;expected&quot; feels a bit off to me.<p>Amortized O(f) strongly suggests that the sum of n operations is very very close to O(n×f). I wouldn&#x27;t say hashmap insertion is amortized O(1), because if you craft input that always incurs a hash collision, then n insertions is much worse than O(n). I <i>would</i> say that it&#x27;s expected O(1), meaning that with high probability an insertion takes constant time.<p>Conversely, &quot;amortized&quot; is only a useful description when it is known that some operations will take much longer than others, yet the total time is bounded. (If you bring up amortized time, you&#x27;re pretty much implying that the distribution of times is uneven, otherwise you wouldn&#x27;t have mentioned it.)<p>For example, if you&#x27;re doubling the length of an array on overflow, then I would say the amortized time of a push is O(1). It would seem weird to say that the <i>expected</i> time is O(1). If I wanted to be more complete, I&#x27;d say &quot;normally a push is constant time, but when the array needs to be expanded then it&#x27;s O(n). The amortized time is still constant, though.&quot;<p>Expected time refers to a single operation. Amortized time describes the mean time of a series of operations.