I've seen ~O(1) as amortized constant time fairly frequently.