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

Reading Big O

Drop the constants, keep the fastest growing term.

The rules

Keep the term that grows fastest and throw away constants and smaller terms. So 3n + 50 is O(n), and n squared plus n is O(n squared).

  • Sequential loops add, so n plus n is still O(n).
  • Nested loops multiply, so a loop inside a loop over the same input is O(n squared).

What n means

Always say what n counts: rows, characters, nodes, pixels. Two inputs get two letters, as in O(n times m) for comparing two lists.