The time being amortized to O(1) means that not only the average is O(1), but it is guaranteed that your use case will average into O(1) if you do enough operations. There is no chance you'll get an O(n^0.5) run just because you got bad data or unlucky.