"Amortized O(1) time" means the time for n operations is O(n), even though individual operations might be more than O(1). Building the hash table means adding

"Amortized O(1) time" means the time for n operations is O(n), even though individual operations might be more than O(1). Building the hash table means adding n things. So they're saying its linear.