MEPX
Chapter 8 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 8 of 12

Space complexity

Memory grows too.

Counting extra memory

Space complexity counts what an algorithm allocates beyond the input. A standard merge sort needs a buffer the size of the input, so it costs O(n) space.

  • In-place sorts such as heap sort use O(1) extra space.
  • Recursion costs stack space: depth d means O(d) even with no allocation.

Trading one for the other

Caching results, indexes and lookup tables buy time with memory. Streaming and recomputation buy memory with time. Most optimisation is choosing which one you can afford.