iwantcoding.com
🔥 Daily 👥 Rooms 🏆 Top Log in Sign up

Complexity Cheatsheet

By · Reviewed & last updated · Part of Data Structures & Algorithms

Big-O is the language of "will this scale". Master the rules of thumb — drop constants, pick the dominant term, separate time and space — and you can predict whether a function is fast enough before running it.

Big-O patterns by data structure and operation

EXAMPLE
# ===== 1) Notation =====
# O(f(n))   upper bound (worst case)
# Ω(f(n))   lower bound (best case)
# Θ(f(n))   tight bound (worst + best are same order)
# We care about O for capacity planning; Θ for accurate descriptions.

# ===== 2) Rules =====
# - Drop CONSTANTS:   3n + 5 -> O(n)
# - Drop LOWER ORDER: n^2 + n -> O(n^2)
# - Loops MULTIPLY: nested for loops over n -> O(n^2)
# - Sequential additions ADD; the largest term wins: O(n) + O(log n) = O(n)
# - Recurrences: use master theorem (see dsa/divide lesson)

# ===== 3) Common complexities (sorted slowest growth first) =====
# O(1)         constant
# O(log n)     halving each step (binary search)
# O(sqrt n)    rare; some number-theoretic algorithms
# O(n)         single pass
# O(n log n)   sorting; divide-and-conquer
# O(n^2)       nested loops over the input
# O(n^3)       triple-nested (Floyd-Warshall on small graphs)
# O(2^n)       subsets, brute-force backtracking
# O(n!)        permutations

# Rough rule on a modern CPU (1s budget):
# O(n^2) feasible up to ~10^4
# O(n log n) feasible up to ~10^7
# O(n)     feasible up to ~10^8
# O(2^n)   feasible up to ~25

# ===== 4) Data-structure ops =====
# Array (fixed size):       index O(1); search O(n); insert/delete O(n)
# Dynamic array (Vec/List): index O(1); push amortised O(1); insert middle O(n)
# Linked list:              index O(n); insert/delete at known node O(1); search O(n)
# Hash map (HashMap/dict):  insert/get/delete avg O(1); WORST O(n) on bad hash
# Balanced BST (TreeMap):   insert/get/delete O(log n); range O(log n + k)
# Heap (priority queue):    push/pop O(log n); peek O(1)
# Trie:                     ops O(L) where L is the key length
# Disjoint set (Union-Find): nearly O(1) amortised (inverse Ackermann)
# Skip list:                like balanced BST in practice
# Bloom filter:             insert/contains O(k) where k is hash count

# ===== 5) Algorithms cheat =====
# Sorting (Timsort, IntroSort): O(n log n) worst case
# Binary search:                O(log n)
# Linear search:                O(n)
# Mergesort, heapsort:          O(n log n) deterministic
# Quicksort:                    O(n log n) expected; O(n^2) worst (pathological)
# Quickselect:                  O(n) expected; O(n^2) worst
# Dijkstra:                     O((V + E) log V) with a heap
# BFS / DFS:                    O(V + E)
# Floyd-Warshall:               O(V^3)
# Union-Find Kruskal MST:       O(E log E)
# Knapsack DP:                  O(nW) — pseudo-polynomial
# Edit distance DP:             O(n * m)
# Knuth-Morris-Pratt:           O(n + m)
# Rabin-Karp:                   expected O(n + m), worst O(nm)

# ===== 6) Space matters too =====
# Many 'fast' algorithms use lots of memory. Note when space is the bottleneck.
# In-place sort:  O(1) extra (heapsort, in-place quicksort)
# Mergesort:      O(n) extra
# Tabulation DP:  O(state-space) — sometimes the killer

# ===== 7) Worst vs average vs amortised =====
# - Worst:   the upper bound on a single call
# - Average: expected over inputs (hash-map insert)
# - Amortised: per-call cost averaged over a SEQUENCE
#   (dynamic array push: occasional O(n) resize, amortised O(1))

# ===== 8) When does Big-O lie? =====
# - Constants matter on real hardware (cache locality)
# - Small N: O(n^2) bubble sort can beat O(n log n) mergesort for n < 16
# - Hidden allocations: O(n) with malloc per element is slower than O(n) on a preallocated buffer
# - Concurrent code: contention can dominate the asymptotic class
# Profile to confirm Big-O predictions on your real inputs.

# ===== 9) Recipes for spotting the class =====
# - 'For each pair' -> O(n^2)
# - 'Halve the search space' -> O(log n)
# - 'Sort then sweep' -> O(n log n)
# - 'Hash table by key' -> O(n) amortised
# - 'For each subset' -> O(2^n)
# - 'For each permutation' -> O(n!)

# ===== 10) Self-test =====
# Match each to its complexity:
# - Two-pointer linear scan over sorted input          -> O(n)
# - Binary heap top-K                                  -> O(n log k)
# - Bellman-Ford shortest path                          -> O(VE)
# - 0/1 knapsack                                        -> O(nW)
# - Brute-force subset sum                              -> O(2^n)
# - Trie autocomplete with prefix p over D dict words  -> O(p) lookup

Why it matters

Sketch the complexity BEFORE writing the code, then compare to the worst-case input size. Most production "why is this slow?" bugs are O(n^2) hidden inside an O(n) wrapper — spotting them at design time costs minutes; spotting them after a customer complaint costs days.

Tip: Tweak the snippet with Try it Yourself », then sit the quiz at the bottom of the page.

Example

Example
// Standard collection costs (typical):
// Array push / pop      O(1) amortised
// HashMap get / set     O(1) amortised
// TreeMap get / set     O(log n)
// Sorted array search   O(log n)
// Heap push / pop       O(log n)
// String concat in loop O(n^2)  — use a list + join instead
Try it Yourself »

Discussion

Loading…