What does amortized complexity mean?

Amortized complexity is the average cost of one operation when looking at a long sequence of operations, including rare "expensive" cases.

In simpler terms, it shows how much an operation costs on average if the rare costs are spread across all the steps.

---

#1. Example: dynamic array

When a dynamic array (for example, Python's list or C++'s vector) fills up, it occasionally expands:

• if there is enough room → the insertion takes O(1);
• if the room has run out → a new array twice as large is created, and all elements are copied (O(n)).

But such copying happens rarely: after each expansion, hundreds of fast O(1) insertions run again.

If you count all insert operations over a long time and divide the total time by the number of insertions, you get an average cost of ≈ O(1).

This is exactly the amortized complexity of insertion, O(1).

---

#2. Analogy

Imagine you're walking down a road, and every step costs 1 second, but once every 100 steps you put on new boots, which costs 10 seconds. The average time per step still stays around 1 second, this is cost amortization.

---

#3. Why this is needed

Amortized complexity helps assess the real efficiency of data structures, where:

• most operations are cheap,
• but rare "spikes" in cost happen occasionally.

---

#4. Formally

If, over (n) operations, the total cost was (T(n)), then the amortized cost of one operation is:

[ \text{A}(n) = \frac{T(n)}{n} ]

---

Summary:

Amortized complexity shows the average cost of one operation in a sequence, smoothing out the rare expensive cases (for example, when a dynamic array expands).