Glossary: Data Structures and Algorithms in Java
amortized O(1)
Also written: amortized
A cost that is occasionally slow but averages out to constant time over many operations. `ArrayList.add(x)` at the end is amortized O(1) because the rare move to a bigger block is spread over many adds.
Where the book teaches it
Related terms
dynamic arraycapacityBig-O shapes (O(1), O(log n), O(n), O(n log n), O(n²), O(V + E))