Big-O Notation Cheat Sheet

• Constant & Logarithmic
  • O(1): hash table lookup, array access by index
  • O(log n): binary search on a sorted array
• Linear & Linearithmic
  • O(n): single pass, linear search
  • O(n log n): merge sort, heap sort, most built-in sorts
• Quadratic & Worse
  • O(n²): nested loops over the same array, bubble sort
  • O(2ⁿ): naive recursive Fibonacci
  • O(n!): brute-force over all permutations
• How to Read Big-O
  • Describes growth rate, not exact running time
  • Constants and lower-order terms are dropped
  • Always ask: worst case or average case?
• Practical Rules
  • n up to ~10⁶: aim for O(n log n) or better
  • Memoization can turn exponential into polynomial
  • Hash maps trade memory for O(1) lookup