Algorithms & Big-O Cheat Sheet
Covers common Big-O complexity classes with code examples, plus rules of thumb for analyzing worst-case and amortized runtime.
1 PageBeginnerMar 30, 2026
Common Complexity Classes
Growth rates ordered from fastest to slowest.
- O(1) - Constant- Runtime doesn't depend on input size, e.g. array index access or a hash map lookup
- O(log n) - Logarithmic- Runtime grows slowly as input doubles, e.g. binary search or balanced BST operations
- O(n) - Linear- Runtime grows proportionally with input size, e.g. a single loop through an array
- O(n log n) - Linearithmic- Typical of efficient sorting algorithms like merge sort and heapsort
- O(n^2) - Quadratic- Runtime grows with the square of input size, e.g. nested loops or bubble sort
- O(2^n) - Exponential- Runtime doubles with each additional input element, e.g. naive recursive Fibonacci or brute-force subsets
Complexity in Code
Concrete examples of each common complexity class.
python
# O(1): constant timedef get_first(arr): return arr[0]# O(log n): binary searchdef binary_search(arr, target): lo, hi = 0, len(arr) - 1 while lo <= hi: mid = (lo + hi) // 2 if arr[mid] == target: return mid elif arr[mid] < target: lo = mid + 1 else: hi = mid - 1 return -1# O(n log n): merge sort's recurrence# T(n) = 2T(n/2) + O(n)# O(n^2): nested loop over all pairsdef has_duplicate_pair(arr): for i in range(len(arr)): for j in range(i + 1, len(arr)): if arr[i] == arr[j]: return True return False
Analysis Rules of Thumb
How to reason about Big-O correctly.
- Drop constants- O(2n) and O(n) are both written O(n) — Big-O describes growth rate, not exact operation counts
- Worst vs average case- Big-O typically describes worst case; Big-Theta (Θ) is a tight bound, Big-Omega (Ω) is the best case
- Space complexity- Measures extra memory used relative to input size, analyzed the same way as time complexity
- Amortized analysis- Average cost per operation over a sequence, e.g. dynamic array append is O(1) amortized despite occasional O(n) resizes
- Dominant term- Only the fastest-growing term matters as n approaches infinity, e.g. O(n^2 + n) simplifies to O(n^2)
Pro Tip
Big-O hides constant factors — an O(n) algorithm with a large constant can be slower in practice than an O(n log n) one for realistic input sizes, so benchmark before optimizing blindly.
Was this cheat sheet helpful?
Explore Topics
#AlgorithmsBigO#AlgorithmsBigOCheatSheet#Programming#Beginner#CommonComplexityClasses#ComplexityInCode#AnalysisRulesOfThumb#Covers#OOP#Algorithms#CheatSheet#SkillVeris
