Algorithms · 6 min read

The Big-O cheat sheet that finally clicks

Big-O isn't about how fast your code runs. It's about how the runtime grows as the input grows. Once you internalize that, the rest is memorization.

The eight you actually need

You will encounter dozens of complexity classes in textbooks. In the field you mostly hit these eight. The bar shows growth at n = 1,000.

O(1)

Instant · "Constant"

Hash table get dict[key]
Array index arr[i]
Stack push/pop

O(log n)

Excellent · "Logarithmic"

Binary search
B-tree index lookup
Heap insert/extract

O(n)

Good · "Linear"

Array scan
Linked list traversal
Counting

O(n log n)

Fine · "Linearithmic"

Merge sort, quicksort
Heap sort
FFT

O(n²)

Avoid for large n · "Quadratic"

Bubble / insertion sort
Nested loop over the same array
Naive pairwise comparison

O(n³)

Slow · "Cubic"

Naive matrix multiplication
Floyd-Warshall shortest path
3-nested loops

O(2ⁿ)

Hard · "Exponential"

Naive recursive Fibonacci
Brute-force subset enumeration
SAT solving (worst case)

O(n!)

Intractable · "Factorial"

Brute-force TSP
Permutation generation
Anything with "try every order"

How big is "n" allowed to be?

Practical limits assuming a 1-second budget on a modern laptop. Treat these as a vibe check, not a contract.

Complexity	Max n before it hurts	Real-world example
O(1)	any size	Redis GET
O(log n)	10²⁰	Indexed Postgres lookup
O(n)	10⁸	Stream through a CSV
O(n log n)	10⁷	Sorting a million items
O(n²)	10⁴	Nested loop over a request batch
O(n³)	500	3-table join with no indexes
O(2ⁿ)	25	Brute-force feature flag combinations
O(n!)	11	Try every flight route

The trick that beats O(n²)

Most quadratic algorithms in production exist because someone wrote a nested loop instead of using a hash. The pattern:

# O(n²) — for each pair, check if they sum to target
for a in nums:
    for b in nums:
        if a + b == target: return (a, b)

# O(n) — one pass, hash the complement
seen = {}
for n in nums:
    if target - n in seen: return (target - n, n)
    seen[n] = True

The 80/20 rule: in real systems, you almost never need anything fancier than O(n log n). If you're tempted to write O(n²), ask: can I sort first? Can I use a hash? Can I cache? Three questions, three escapes.

Three lies your intuition will tell you

Lie 1: "It's only a small loop." A nested loop over a 10k-item request batch is 100,000,000 iterations. That's 5+ seconds in Python. Profile before defending.

Lie 2: "O(log n) and O(n) are basically the same." Not at scale. log₂(10⁹) ≈ 30. The linear version is 33 million times slower at a billion items.

Lie 3: "The constant doesn't matter." It does for small n. 100·n beats n² only when n > 100. For tiny inputs, the "worse" algorithm can win.