Before You Start
Imagine that we have a hash table with an ideal hash function (one that uniformly randomly assigns buckets to keys) that uses separate chaining and dynamic resizing.
Say that we insert \( m \) keys and then look up each key (i.e., \( m \) lookups).
We have an amortized expected complexity for insert of \( \Theta(1) \).
As a result, we don't know the expected complexity for any individual insert (could be linear time or better), but we do know that \( m \) inserts into an initially empty table will have an expected complexity of \( \Theta( 1 + 1 + 1 + \cdots{} + 1 ) = \Theta(m) \).
For lookup we have an expected complexity of \( \Theta(1) \).
Therefore the expected complexity of each individual lookup is constant time, so the expected complexity for all \( m \) of them would be \( \Theta(1) + \Theta(1) + \cdots{} + \Theta(1) = \Theta(m) \).
All together, our expected complexity for this sequence is \( \Theta(m) \).
What about worst-case complexity?
The worst-case complexity for both insert and lookup is \( \Theta(n) \) and our amortized bound for insert is only for expected complexity (not worst-case complexity).
So in the worst case, thanks to our bad hash function, we build a single long chain in one bucket.
In that case, for each insert we perform an unsuccessful look up on a longer and longer chain. So the complexity of the inserts would be \( \Theta( 1 + 2 + 3 + \cdots + ( m - 1 ) ) = \Theta(m^2) \).
For each lookup we find one key, and each key requires a different number of comparisons to find. So the complexity of the lookups would be \( \Theta( 1 + 2 + 3 + \cdots + m ) = \Theta(m^2) \).
All together, the overall worst-case complexity is \( \Theta(m^2) \).
(When logged in, completion status appears here.)