What is amortized complexity?

Amortized complexity is the average cost of an operation in a sequence of operations, averaged over all operations, including rare expensive ones.

Unlike the worst-case scenario for a single operation, amortized complexity shows how much an operation costs on average during long-term execution of an algorithm or data structure.

Example: dynamic array (ArrayList) when adding elements.

• Usually, adding an element is an O(1) operation.
• But when the array is filled, memory reallocation and copying of elements occur — an O(n) operation.

The amortized complexity of adding remains O(1) because expensive operations happen rarely, and their cost is spread over many cheap operations.

This helps evaluate the efficiency of algorithms and data structures in real-world conditions, not just in worst-case scenarios.