The add operation runs in amortized constant time,...

# random

[jo]

The add operation runs in amortized constant time, that is, adding n elements requires O(n) time. All of the other operations run in linear time (roughly speaking).