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

Best, average and worst

One algorithm, three answers.

Which one to quote

Best case is usually useless, average describes normal behaviour, and worst case is what you promise. Quote the average when describing typical performance and the worst when it matters for safety.

  • Quicksort: O(n log n) average, O(n squared) worst.
  • Hash map lookup: O(1) average, O(n) worst.

Adversarial input

A worst case that never happens by accident can be provoked on purpose. Attacks that force hash collisions turn a fast lookup into a linear scan, which is why libraries randomise their hashes.