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)
Master Theorem for Divide-and-Conquer
Solving recurrences of the form T(n) = aT(n/b) + f(n) without unrolling them by hand.
text
T(n) = a*T(n/b) + f(n), a >= 1, b > 1Compare f(n) to n^(log_b a):Case 1: f(n) = O(n^(log_b a - e)) for some e > 0 => T(n) = Theta(n^(log_b a)) [work dominated by leaves]Case 2: f(n) = Theta(n^(log_b a) * log^k n), k >= 0 => T(n) = Theta(n^(log_b a) * log^(k+1) n) [work balanced]Case 3: f(n) = Omega(n^(log_b a + e)) and a*f(n/b) <= c*f(n) for c<1 => T(n) = Theta(f(n)) [work dominated by root]Examples: Merge sort: T(n) = 2T(n/2) + O(n) -> Case 2, k=0 -> Theta(n log n) Binary search: T(n) = T(n/2) + O(1) -> Case 2, k=0 -> Theta(log n) Karatsuba mult.: T(n) = 3T(n/2) + O(n) -> Case 1 -> Theta(n^log2(3)) ~ n^1.585 Strassen matmul: T(n) = 7T(n/2) + O(n^2) -> Case 1 -> Theta(n^log2(7)) ~ n^2.807
Amortized Analysis: The Accounting Method
Proving a dynamic array's append is O(1) amortized by pre-charging extra 'credit' on cheap operations to pay for expensive resizes.
python
class DynamicArray: """Doubling dynamic array -- illustrates amortized O(1) append. Accounting method: charge 3 'credits' per append. - 1 credit pays for inserting the new element now. - 2 credits are banked on the element for a future resize. When a resize to size 2n happens, the n elements already carrying 2 banked credits each pay for their own copy (n*2 = 2n available, exactly enough to copy all n old elements). Credit never goes negative, so the amortized cost per append is O(1) even though individual resizes cost O(n). """ def __init__(self): self._data = [None] * 1 self._size = 0 def append(self, x): if self._size == len(self._data): self._resize(2 * len(self._data)) # O(n), but rare self._data[self._size] = x self._size += 1 # O(1), the common case def _resize(self, new_cap): new_data = [None] * new_cap for i in range(self._size): new_data[i] = self._data[i] self._data = new_data
Beyond Big-O: P, NP, and NP-Complete
How complexity theory classifies problems by decision difficulty, and why greedy/DP shortcuts don't exist for NP-complete problems.
text
P - solvable in polynomial time, e.g. sorting O(n log n), shortest path via Dijkstra O((V+E) log V)NP - a proposed solution can be VERIFIED in polynomial time, even if finding one may take exponential time (P is a subset of NP: anything solvable in P is also verifiable in P)NP-complete - the hardest problems in NP: every other NP problem reduces to them in polynomial time e.g. 3-SAT, Traveling Salesman (decision form), Knapsack (decision form), Graph ColoringNP-hard - at least as hard as NP-complete, but not necessarily in NP itself (may not even be a decision problem), e.g. the optimization form of TSPPractical implication: if a problem is proven NP-complete, stopsearching for a polynomial exact algorithm -- instead reach for: - approximation algorithms (bounded error, polynomial time) - heuristics (no guarantee, fast in practice) - exponential exact algorithms with pruning (branch-and-bound, ILP) - restricting to a tractable special case of the input
Recurrence Relations for Recursive Cost
Translating recursive call structure directly into a recurrence, then classifying its growth without a full recursion-tree expansion.
python
# Naive recursive Fibonacci: T(n) = T(n-1) + T(n-2) + O(1)# Two subproblems each only slightly smaller than n -> the call tree# has ~golden-ratio branching -> T(n) = O(phi^n), phi ~ 1.618def fib(n): if n <= 1: return n return fib(n - 1) + fib(n - 2)# Memoized Fibonacci: each of the n distinct subproblems is computed# once in O(1) work (after its dependents are cached) -> T(n) = O(n)def fib_memo(n, cache={}): if n in cache: return cache[n] if n <= 1: return n cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache) return cache[n]# Quickselect (average case): T(n) = T(n/2) + O(n) on a lucky pivot# -> geometric series sums to O(n) total, not O(n log n), because# work shrinks geometrically per level while total work per level# also shrinks (only one branch is recursed into, unlike merge sort).
Complexity Terms Beyond the Basics
Vocabulary that shows up once you move past classifying single functions.
- Big-Omega (Omega)- Asymptotic lower bound: describes the best case or a guaranteed minimum growth rate
- Big-Theta (Theta)- Tight bound: growth rate is sandwiched between a constant multiple of the same function from above and below
- Polynomial vs exponential time- The line between 'scales to large n' (P) and 'infeasible past small n' (exponential); NP-hardness lives on the exponential side
- Amortized vs worst-case per-operation- Amortized bounds the average cost over a sequence of operations; a single operation can still spike above it (e.g. one O(n) resize)
- Competitive ratio- For online algorithms (decisions made without seeing future input), the worst-case ratio of the algorithm's cost to the optimal offline cost
- Space-time tradeoff- Trading memory for speed (memoization, lookup tables, precomputed indexes) or vice versa (recomputation, streaming instead of buffering)
- Pseudo-polynomial time- Runtime polynomial in the numeric VALUE of the input (e.g. O(nW) for 0/1 knapsack) rather than its bit-length -- technically exponential in input size for large numbers
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#Master#OOP#Algorithms#CheatSheet#SkillVeris
