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

Logarithmic time

Halving the problem each step.

Where log n comes from

If each step throws away half of what is left, the number of steps is the logarithm of n. A million items take about twenty steps, which is why binary search feels like magic.

  • Binary search needs sorted input, and sorting first costs O(n log n).
  • Balanced trees give O(log n) insert, delete and lookup for the same reason.

The base does not matter

Log base 2 and log base 10 differ by a constant factor, and constants are dropped, so the notation just says O(log n).