They are not the same. "Expected" refers to the running time of a single operation when it uses randomness. "Amortized" talks about what happens when you call t

They are not the same. "Expected" refers to the running time of a single operation when it uses randomness. "Amortized" talks about what happens when you call the same operation multiple times (it has nothing to do with randomness). Hash maps provide O(1) expected lookups. This running time relies on randomness, and it is the average running time of one operation. If you are very unlucky (or if an attacker can predict your random number generator), then it is possible for every single lookup to run in O(n) time. Dynamic arrays (vector in C++, ArrayList in Java) provide O(1) amortized push calls. Dynamic arrays sometimes have to copy every element in the array into a new allocation when you call push. However, by doubling the size every time this happens, the copies happen so rarely that if you push k times (starting with an empty array), then the total running time of all k calls is O(k), even though a small number of the calls are much more expensive than O(1). So, unlike expected running times, an amortized running time of O(f(n)) is an absolute guarantee that calling it k times in a row never runs slower than O(k*f(n)).