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

Recursion and recurrences

Working out the cost of a divide and conquer.

Reading a recurrence

Merge sort splits into two halves and does linear work to merge, written T(n) = 2T(n/2) + O(n). That solves to O(n log n): log n levels, each doing O(n) work.

  • Binary search is T(n) = T(n/2) + O(1), which gives O(log n).
  • Naive Fibonacci is T(n) = T(n-1) + T(n-2), which is exponential.

Memoisation

Storing results of subproblems turns exponential recursion into linear work. That is the whole idea behind dynamic programming, and it is a space for time trade.