Suggest an editImprove this articleRefine the answer for “What does amortized complexity mean?”. Your changes go to moderation before they’re published.Approval requiredContentWhat you’re changing🇺🇸EN🇺🇦UAPreviewTitle (EN)Short answer (EN)**Amortized complexity** is the average cost of one operation when looking at a long sequence of operations, including rare "expensive" cases. **Key point:** for a dynamic array, appending to the end has amortized complexity O(1), because the rare expensive expansions (O(n)) are spread across hundreds of fast O(1) insertions.Shown above the full answer for quick recall.Answer (EN)Image**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).For the reviewerNote to the moderator (optional)Visible only to the moderator. Helps review go faster.