tl;dr: Each insertion is O(n), but n insertions are also O(n). Saying "amortized time is O(1)" just means the time for n operations is O(n). To be pedantic: s

tl;dr: Each insertion is O(n), but n insertions are also O(n). Saying "amortized time is O(1)" just means the time for n operations is O(n). To be pedantic: some individual insertions can take more the O(1), namely when you have to rehash it can take O(n) time. So the tight upper bound on each insertion is O(n). So doing n of them seems like it might take O(n^2). Except you can't rehash on every insertion. So even though the time to insert one is O(n), the time to insert n is also O(n). If you amortize that time over all n insertions, you get O(n) / n == O(1).