Big-O Notation Cheat Sheet for Working Engineers

Big-O describes how an algorithm scales with input size. This cheat sheet is the minimum useful subset for engineers shipping production code — common operations, their complexities, and the trade-offs you actually face when picking a data structure.

1. The complexity hierarchy

From fastest to slowest, with concrete examples:

Practical limit: Modern hardware does ~10⁸–10⁹ simple operations per second. Anything beyond 10¹⁰ total operations is too slow for real-time use. A request with O(n²) on n=100k is already 10¹⁰ ops — you'll feel it.

2. Data structure operation complexities

3. Sorting algorithms

What your language uses: Python and Java's Arrays.sort use Timsort (a mergesort variant optimized for partially-sorted data). C++ std::sort uses introsort (quicksort + heapsort fallback). Rust uses a stable sort based on Timsort.

4. Graph algorithm complexities

Where V = vertices, E = edges:

• BFS / DFS: O(V + E)
• Dijkstra (binary heap): O((V + E) log V)
• Bellman-Ford: O(V·E) — handles negative weights
• Floyd-Warshall (all pairs): O(V³)
• Topological sort: O(V + E)
• Minimum spanning tree (Kruskal): O(E log E)

5. Common patterns and their complexity

// O(1) — constant
arr[42]
hashMap.get(key)

// O(log n) — halving the search space
binarySearch(sortedArr, target)
balancedTree.insert(value)

// O(n) — single loop or scan
arr.filter(x => x > 0)
linkedList.find(value)

// O(n log n) — sort + linear, or divide-and-conquer
arr.sort()
mergeSort(arr)

// O(n²) — nested loops over the same input
for (i = 0; i < n; i++) {
  for (j = 0; j < n; j++) {
    // pair work
  }
}

// O(n + m) — two separate inputs
arr1.concat(arr2)
mergeSorted(a, b)

6. Space complexity gotchas

Space complexity often gets ignored, but matters as much as time in memory-bounded systems:

• Recursion depth: Recursive algorithms use O(depth) stack space. A naive recursive Fibonacci uses O(n) stack — and stack overflows are real.
• Auxiliary vs total: Mergesort is "O(n) extra space" — that's auxiliary. Heapsort is in-place (O(1) auxiliary). For limited RAM, in-place wins.
• Hash map memory overhead: Open-addressing hash maps typically use 1.5–2× the slots needed (load factor 0.5–0.7). A million-entry map can cost 100MB+.

7. When Big-O lies

Big-O hides constant factors — and constants often dominate at small scale:

• Cache locality: Linear scan over a contiguous array (O(n)) is often faster than O(log n) tree search at small n, because the array fits in L1/L2 cache.
• SIMD / vectorization: Modern CPUs process 4–8 elements per cycle for simple operations. An "O(n)" linear scan can be 10× faster than expected.
• Memory allocation: A "free" O(1) hash insert that triggers a rehash is suddenly O(n). Amortized analysis covers this, but a single request can still spike.

Rule of thumb: Choose data structures by Big-O. Profile before optimizing constants.

FAQ

References

• Big O notation — Wikipedia
• Big-O Cheat Sheet (community reference)
• Introduction to Algorithms (Cormen, Leiserson, Rivest, Stein) — the canonical CS textbook
• Python data types performance