Data Structures22 min read
Amortized Analysis
Understand why some operations look expensive but are cheap on average, using list resizing and append behavior as your main intuition.
David Miller
December 21, 2025
0.0k0
Sometimes an operation looks slow once, but overall it is fast across many runs.
This idea is called **amortized analysis**.
Why this matters Beginners often think: “append() sometimes resizes list, so it must be slow”.
But in reality: - resizing happens rarely - most appends are O(1) - overall cost stays low
Example: list append ```python nums = [] for i in range(100000): nums.append(i) ```
Most appends are fast. Occasionally Python resizes internal array.
Intuition Instead of asking: “How slow is one operation?” We ask: “How slow is it on average over many operations?”
Visual idea ```mermaid flowchart LR A[Many cheap appends] --> B[One expensive resize] B --> C[Overall still fast] ```
Key takeaway - append() is amortized O(1) - occasional slow step doesn’t break overall speed
Remember - Amortized = average over time - Python lists are optimized for growth
#Python#Advanced#Performance