MEPX
Chapter 9 of 12All chapters
  1. 1Why complexity matters
  2. 2Reading Big O
  3. 3Constant and linear time
  4. 4Logarithmic time
  5. 5Sorting and its floor
  6. 6Quadratic and worse
  7. 7Best, average and worst
  8. 8Space complexity
  9. 9Amortised analysis
  10. 10Costs by data structure
  11. 11Recursion and recurrences
  12. 12Choosing an algorithm

Chapter 9 of 12

Amortised analysis

Rare expensive steps, spread out.

The dynamic array

Appending to a dynamic array is O(1) amortised. Most appends write into spare capacity, and the occasional resize copies everything, but because capacity doubles the copies are rare enough to average out.

  • Amortised is an average over a sequence of operations, not a probability.
  • A single append can still be O(n). Real time systems care about that.

Elsewhere

Hash maps rehash on growth for the same reason, and the same argument applies. Whenever you see doubling, expect an amortised claim.