The worst-case is indeed arbitrarily long, but the amortized runtime can be analyzed.

See: http://en.wikipedia.org/wiki/Amortized_analysis