O(1). That is, the amortized time per operation is bounded by a constant. More precisely, n operations take time O(n).