Big O Notation

01Why a notation, not a stopwatch

A naive collision check on the entities in a scene is two nested loops: for every pair of entities, test whether they overlap. On the four-object test scene that's six comparisons; the function takes 200 nanoseconds and nobody profiles it. On the eight-hundred-object shipping scene that's roughly 320,000 comparisons, the function takes 6 milliseconds, and a third of a 60 fps frame is gone before any contact has been resolved. A stopwatch on day one tells you nothing about day three hundred. A notation that says this function does work proportional to n² does, because the multiplier the player will pay was visible the moment the function was written.

Big O notation is that language. It strips a function down to its dominant growth term and throws away everything else (constants, lower-order terms, the specific hardware). What's left is the shape of the curve, which largely decides whether a system survives the jump from test scene to shipping content. The shape is independent of the CPU: it describes how the cost grows as the workload does.

The shape that ate the encounter

The widget below plots three implementations of "find all pairs of objects that might be touching": brute force at O(n²), sweep-and-prune at roughly O(n log n), and a uniform spatial hash at O(n + k). Drag the object-count slider:

02A short history of writing down growth rates

Big O was invented for analytic number theory, not computer science, and its modern shape took about 80 years to settle. The current usage makes more sense with the history in view:

03The definition, picked apart

Big O is defined for functions from non-negative integers (or reals) to non-negative reals. The formal statement, the way Knuth wrote it^[10] and CLRS teaches it^[11]:

Read aloud: "f(n) is O(g(n)) if there exist constants c and n₀ such that for every n at least n₀, f(n) is sandwiched between zero and c times g(n)." The c is what lets you throw away constant factors; the n₀ is what lets you throw away lower-order terms. Both are existential, which means the definition is satisfied as soon as you can find any pair that works.

The three things this definition does not say are at least as important as what it does say:

• It is not an equation. The "=" in "f = O(g)" is read "is" or "is in," not "equals." Some authors write f ∈ O(g) to make the set membership explicit, which is more precise. The "=" is convention because that's how Bachmann wrote it^[7].
• It is one-sided. Big O gives an upper bound. f(n) = O(n²) is true if f grows like n², but also if f grows like n, or n log n, or any slower function. Saying "linear search is O(n²)" is technically correct and almost always misleading.
• It is asymptotic. Big O makes no claim about small n. An algorithm that is O(n) can be slower than one that is O(n²) on every input you ever feed it, as long as the latter's n² is multiplied by a small enough constant. The classic example: insertion sort beats quicksort below a few dozen elements, which is why most production sorts cut over to insertion sort at small sizes (libstdc++ at 16 elements, MSVC at 32)^[12].

Drag the widget below. The orange curve is f(n); the violet curve is c · g(n) for the chosen c. The vertical line is n₀. Big O holds when the orange curve stays under the violet one for every n to the right of the line:

04Omega, Theta, and the rest of the family

Big O is an upper bound. The full asymptotic toolkit has four cousins. Each is one inequality flip away from the others:

The flip from "big" to "little" is the flip from existential to universal on the constant: big-O finds one c that bounds f above; little-o requires that every positive c eventually bounds f above. That's a much stronger statement: f can't just be no-bigger-than g by some constant, it has to grow strictly slower.

The same function fits five bounds. Θ(n²) is the tightest description (matching upper and lower); the others are looser. "Merge sort is Θ(n log n)" says more than "merge sort is O(n log n)": the Θ statement also rules out merge sort running faster than n log n, which the O statement leaves open.

What about little-o?

Little-o is what you reach for when you want to claim that one function is fundamentally faster-growing than another, not just that one happens to be bigger. The statement 1/n = o(1) says 1/n shrinks to zero, which is the asymptotic version of "1/n vanishes." The statement n log n = o(n²) says no constant multiple of n log n can keep up with n²: the gap between them grows without bound.

Knuth's 1976 paper introduced Θ so that authors could state a tight bound instead of stretching O to cover it^[10]. The looser habit survives anyway: "an O(n log n) sort" almost always means "a Θ(n log n) sort" in practice. Read O() that way unless the author explicitly distinguishes the two.

05The growth zoo, racing

A handful of complexity classes cover most of the algorithms an engine programmer meets. Knowing their shapes lets you read most papers without redoing the algebra:

The "at n=10⁶" column makes the spacing concrete: six orders of magnitude separate O(n) from O(n²), and another six separate O(n²) from O(n³). At a million elements that is the difference between a millisecond, a quarter of an hour, and three decades.

The widget below races them on a log-log plot. On log-log axes a polynomial n^k is a straight line with slope k, which is why log-log is the standard way to compare growth rates by eye:

06When constants lie

Big O drops constants on purpose: a notation that cared about constants couldn't compare implementations across hardware, compilers, or decades. The price is that two algorithms with the same Big O can differ by orders of magnitude in real-world cost, and an algorithm with worse Big O can beat one with better Big O on inputs you'll actually see.

The textbook example is 100n versus n² / 100. The first is O(n); the second is O(n²). By any asymptotic measure, the linear algorithm wins. Solve for the crossover:

Below n = 10,000 the "worse" algorithm is genuinely faster. With these constants, a system that never exceeds 10,000 elements is better off with the quadratic implementation.

What constants stand for in practice

An algorithm's hidden constant absorbs all the per-operation work the abstraction throws away. Three common sources of large constants:

• Cache misses. Norvig's widely quoted ballparks put an L1 hit at ~0.5 ns, an L2 hit at ~7 ns, and a main-memory fetch at ~100 ns^[15] (current cores hit L2 in a few nanoseconds; the DRAM figure still holds). A linked-list traversal that visits n nodes scattered across memory is O(n), and so is a contiguous array traversal, but the list can run an order of magnitude or more slower because every node can be a DRAM round trip while the array streams through the prefetcher.
• Branch mispredictions. A modern out-of-order core has a pipeline 15 to 20 stages deep and keeps hundreds of instructions in flight; a mispredicted branch throws away the speculative work behind it at a cost of roughly 15 to 20 cycles^[16]. An algorithm with a data-dependent branch can lose several-fold to a branch-free alternative with the same Big O when the branch is unpredictable. The small-n fallbacks in production sorts (insertion sort, and sorting networks for a handful of elements) exist for constant-factor reasons like these (call overhead, branch behavior), not asymptotic ones.
• Memory allocation. An O(n) algorithm that calls malloc once per element pays tens to hundreds of nanoseconds per call on a general-purpose allocator (more under lock contention or when the allocator has to ask the OS for pages); the same algorithm with a bump allocator pays a few. The Big O is the same; the frame-time cost is not.

The external-memory model^[31] and the cache-oblivious model that builds on it^[13] formalize the first of these: they count block transfers between cache and memory instead of CPU operations. For data far larger than cache, the transfer count is often the bound that matters and the operation count is the secondary term. Big O over operations stays correct; a serious analysis often needs a second count next to it.

07Worst, best, average, amortized

An algorithm's runtime is a function of its input. Different inputs produce different runtimes. Big O over an algorithm has to specify which inputs you mean:

• Worst case. The runtime on the slowest input of size n. The default. When the literature says "quicksort is O(n²)," this is the case meant.
• Best case. The runtime on the fastest input. Usually less interesting; insertion sort's best case is Θ(n) (sorted input), which matters when inputs arrive nearly sorted.
• Average case. The expected runtime over some distribution of inputs. Quicksort's average is Θ(n log n) when every input order is equally likely. Useful but harder to claim cleanly: the answer depends on what you assume about the input.
• Amortized. The average runtime per operation over a long sequence. std::vector::push_back's amortized cost is O(1) even though individual pushes can cost O(n) when the vector resizes.

Quicksort: the canonical worst-versus-average gap

Quicksort partitions the array around a pivot and recurses on the two sides; the partition leaves both sides in place, so there is no combine step. A pivot at the median splits the array in half, giving the recurrence T(n) = 2T(n/2) + Θ(n), which the master theorem (§8) solves to Θ(n log n). A random pivot is rarely the exact median, but the expected cost still works out to Θ(n log n), about 1.39 n log₂ n comparisons. On an adversarial pivot (always-smallest or always-largest), it produces partitions of sizes 0 and n−1, giving T(n) = T(n−1) + Θ(n), which sums to Θ(n²).

A sorted-or-reverse-sorted input plus a naive first-element pivot triggers the worst case on every recursion. The widget runs a first-element-pivot quicksort on three input patterns:

Amortized: std::vector::push_back

A dynamic array doubles its capacity when full. Most pushes are O(1) (write to the next slot). The pushes that trigger a resize are O(n) (copy every element to a bigger buffer). Worst-case per push is O(n), which badly overstates what a long sequence of pushes costs. Amortized per push, summed over a sequence and divided by length, is O(1).

The proof is a direct sum (the "aggregate method" in the amortized-analysis framework Tarjan formalized in 1985^[17]): n pushes do n single-slot writes plus resize-copies of sizes 1, 2, 4, ..., 2^{⌈log₂ n⌉−1}, each smaller than n. That sum is less than 2n. Total work is less than 3n; per-push amortized cost is at most 3 = O(1).

08The Master Theorem

Most divide-and-conquer algorithms produce a recurrence of the form:

"To solve a problem of size n, do a recursive subsolves each of size n/b, plus f(n) of additional work to combine them." Merge sort is a = 2, b = 2, f(n) = Θ(n). Top-down binary BVH construction with binned SAH splits has the same shape when the splits come out balanced.

The Master Theorem^[11] classifies these recurrences in three cases, depending on whether the recursive work or the combine work dominates. Let c_crit = log_b a:

• Case 1: leaves dominate. If f(n) = O(n^c) with c < c_crit, then T(n) = Θ(n^c_crit). The recursion tree has so many leaves that they outweigh the combine work.
• Case 2: every level costs the same. If f(n) = Θ(n^c_crit), then T(n) = Θ(n^c_crit log n). Each of the log_b n levels does the same amount of work. Merge sort lives here: c_crit = 1, f(n) = Θ(n), total Θ(n log n).
• Case 3: root dominates. If f(n) = Ω(n^c) with c > c_crit, and a regularity condition holds, then T(n) = Θ(f(n)). The top-level combine work is so expensive that the recursion contributes nothing significant.

Worked examples

Six standard divide-and-conquer recurrences and what the theorem says about them:

The lever is the ratio between how many subproblems you make and how fast they shrink. Strassen's algorithm beats the naive cubic matrix multiply by doing 7 half-size multiplications instead of 8, paid for with extra matrix additions that are still Θ(n²) per level; that one fewer recursive call drops the exponent from 3 to log₂ 7. Later results (Coppersmith-Winograd 1990 and the refinements since, down to ω < 2.371339^[18]) lower the exponent with heavier algebraic machinery rather than a small recursion like Strassen's. Of these, only Strassen sees practical use; the rest are galactic (§14).

09Measuring growth empirically

Sometimes the algorithm is too complex to analyze by hand and you have to measure. The classical trick: run it at sizes n, 2n, 4n, 8n, plot on log-log axes, and read the slope.

On log-log axes, T(n) = c · n^k becomes log T = log c + k · log n, which is a straight line with slope k and intercept log c. Eyeballing the slope is a coarse diagnostic: a slope of 1 means O(n), a slope of 2 means O(n²), anything between 1 and 2 is suspicious (could be O(n log n), could be O(n^1.5), hard to tell from slope alone).

A more discriminating test: the doubling ratio. Measure T(n) and T(2n); the ratio T(2n) / T(n) diagnoses the class:

The widget below shows a simulated running-time curve and lets you guess the complexity. The points carry ±9% random noise, standing in for the cache effects, GC pauses, and scheduler hiccups of real measurements, so the diagnosis isn't always exact.

10Case study: broad-phase collision

Broad-phase collision is the classic engine-side O(n²) trap. Physics simulations need to find every pair of objects whose bounding volumes overlap. A naive double-loop checks n(n−1)/2 pairs; at n = 1000 that's 500,000 pairs every frame, or 30 million pair tests per second at 60 fps. At a few nanoseconds per AABB test that is one to a few milliseconds per frame on one core, a large share of a physics budget that is often only a few milliseconds in total, and it quadruples every time n doubles.

Three standard fixes, with different complexity in different regimes:

Sweep-and-prune (sort and sweep)

Sort the bounding-box endpoints along one axis (say X). Two boxes can only overlap on the X axis if neither's max-X is before the other's min-X. Sweep through the sorted endpoints with an active list; when you hit a min-X, add the box to the active list; when you hit a max-X, remove it. Every pair of boxes simultaneously active is a candidate. Repeat on Y and Z; take the intersection.

The first frame's cost is dominated by the initial sort at O(n log n); the sweep itself is O(n + k) where k is the number of active-pair encounters. In subsequent frames the endpoint lists are nearly sorted (objects move a little, not a lot, per step), and insertion sort on a nearly-sorted list runs in O(n + s) where s is the number of out-of-order pair swaps. In steady state that puts per-frame cost at O(n + k + s), which is close to linear when both k and s are O(n). The pathological case (every box overlaps every other) blows k up to O(n²) and you're back to the naive cost. Cohen et al.'s 1995 I-COLLIDE paper is the standard reference for sweep-and-prune with this temporal-coherence trick^[4].

Uniform spatial hash

Partition space into a regular grid. Hash each object's AABB into the cells it touches. Two objects can only collide if they share a cell. Build cost is O(n); query cost is the sum over cells of the per-cell pair-test count.

If average density is d objects per cell and the cell size is at least as large as the biggest object's AABB (so each object touches O(1) cells), the per-cell pair-test count averages d²/2, and total cost is O(n · d), which collapses to O(n) when d is bounded. The catch: d is bounded only when objects are spread out. A pile of crates on the same tile reduces to brute force inside that tile. GPU Gems 3 builds the same kind of grid on the GPU: it radix-sorts (cell, object) pairs so each cell's occupants end up contiguous, then tests them in passes that keep neighboring cells from double-counting a pair^[5].

BVH for moving objects

Build a bounding volume hierarchy over the objects' AABBs and query each object against the tree. Construction is O(n log n); a query costs roughly O(log n) plus the pairs it reports in well-spread scenes, so a full pass is roughly O(n log n + k). Real engines update the tree incrementally as objects move instead of rebuilding it: Bullet's btDbvtBroadphase and Box2D's b2DynamicTree are dynamic AABB trees of this kind. PhysX 5 takes a different route, shipping sweep-and-prune plus a family of box-pruning broad phases, with automatic box pruning (eABP) recommended as the default^[30].

The widget runs all three on the same simulated scene. At low object counts the three work counts are close, and brute force's tiny per-test constant can make it the fastest in wall-clock terms; at high counts it loses by a wide margin:

11Case study: BVH ray traversal

Ray tracing a scene of n triangles by brute force means testing the ray against every triangle: O(n) per ray, O(n · pixels) per image. At n = 10⁷ triangles and a 1080p image that's 2×10¹³ ray-triangle tests per frame, which is several orders of magnitude past tractable.

A bounding volume hierarchy typically brings this down to roughly logarithmic cost per ray. Triangles are organized into a binary tree where each node's AABB encloses every triangle in its subtree. To intersect a ray with the scene, test the ray against the root's AABB; if it misses, the whole subtree is irrelevant. If it hits, visit the children, nearer one first. At a leaf, test the ray against the small bucket of triangles inside. For the closest hit, which is what a renderer usually wants, any node whose box starts farther along the ray than the best hit found so far can be skipped.

The logarithmic behavior is empirical rather than guaranteed. A tree built with the surface-area heuristic (the build Physically Based Rendering walks through^[1]) over reasonably distributed geometry visits a number of nodes per ray that grows roughly with log n. The worst case is still O(n): a ray grazing many overlapping boxes, or geometry such as long thin triangles whose boxes all overlap, can force a visit to most of the tree.

12Case study: A* and the branching factor

A* searches a graph for the shortest path from start to goal. At each step it picks the frontier node with the lowest estimated total cost f(n) = g(n) + h(n), where g is the known cost so far and h is a heuristic estimate to the goal. With an admissible heuristic, A* returns an optimal path^[20]; with no heuristic, it degenerates to Dijkstra; with a perfect heuristic (and ties broken toward the goal), it expands only nodes on an optimal path.

The textbook worst case for A* as a tree search is O(b^d), where b is the branching factor (how many neighbors a node has) and d is the depth of the solution. With a closed set that never expands a node twice, the search is also bounded by the size of the graph: O(E log V) with a binary-heap open list. On a 2D grid b = 4 (von Neumann) or b = 8 (Moore neighborhood); on a navmesh b is the number of neighbors per polygon, 3 for a triangle mesh and up to 6 for Recast's default convex polygons.

The exponential isn't in n (the size of the graph); it's in d (how far the goal is). On a 100×100 grid with the goal 50 steps away, a tree search that didn't track visited nodes would expand on the order of 4⁵⁰ nodes; with a visited set, BFS expands at most the grid's n = 10⁴ cells (an unobstructed diamond of radius 50 holds about 5,100). A* with a good heuristic on an open map expands a few nodes per step of path, a few hundred in total: the visited region is a corridor along the optimal path, not a diamond.

The heuristic's quality is the lever. A perfect heuristic (the true remaining distance) keeps the search on an optimal path. An admissible but loose heuristic (Manhattan distance on a grid with obstacles) makes A* explore a fan along the path. An inadmissible heuristic (one that can overestimate) usually makes A* faster, but the result is no longer guaranteed optimal:

13Case study: sorting draw calls

A renderer can issue thousands of draw calls per frame. Reordering them to group calls that share a render target, shader, or material cuts the number of state changes, which cost CPU time in the driver and can stall the GPU^[2].

A common pattern: every draw call gets a 32- or 64-bit sort key packing render target, shader, material, depth, and so on into bit fields in priority order. Sort the array of keys. Issue the calls in the sorted order. The sort's cost matters because the renderer runs it every frame:

• std::sort (introsort). O(n log n) comparison-based. On a uniformly random array of 64-bit keys, modern x86 implementations take on the order of a few milliseconds per 100,000 elements. Partially sorted input is usually faster: branches become more predictable, and pdqsort-derived sorts such as current libc++ also detect partitions that are already in order.
• Radix sort. O(d · n) where d is the number of digits (typically bytes) in the key. For a 64-bit key with 8-bit digits, d = 8. Tuned implementations beat std::sort on integer keys once n is large; Malte Skarupke's ska_sort, an in-place byte-wise radix sort, is a well-known example with published benchmarks. Below a few hundred elements the fixed per-pass cost (clearing and scanning a 256-entry histogram) hands the win back to the comparison sort, which is why ska_sort itself falls back to std::sort for small ranges.

Why isn't every sort a radix sort? Two reasons. First, comparison sorts work on any type with an ordering; radix sorts need keys that break into digits (integers, floats after a sign-bit flip, strings). Second, a naive radix sort scatters writes across many buckets and misses cache, so the constant is larger than the textbook complexity suggests; the implementations that beat std::sort handle that explicitly. A 2022 Bevy engine issue measured radix against comparison sorting for its render phases, with a large win on one benchmark and regressions on two others^[21]; Christer Ericson's blog post lays out the widely used bit-packing pattern^[2].

Radix sort being O(n) (treating d as a constant for fixed-width keys) sounds like it violates the Ω(n log n) lower bound for sorting. It doesn't: the lower bound's proof counts the leaves of a binary tree of comparison outcomes^[11], so it only covers sorts that learn about the keys through comparisons. Radix sort reads the digits directly.

#include <cstdint>  // uint64_t

// A 64-bit draw-call sort key. Field order is priority order: the most
// significant bits drive the coarsest grouping, so a plain integer
// compare on packed keys yields the draw order.
// Packed with shifts rather than C++ bit-fields: bit-field placement is
// implementation-defined (MSVC and GCC on x86 put the first field in the low
// bits), and a struct of bit-fields has no ordering to sort by anyway.
constexpr int kPassBits = 2, kShaderBits = 10, kMaterialBits = 14, kMeshBits = 14, kDepthBits = 24;
static_assert(kPassBits + kShaderBits + kMaterialBits + kMeshBits + kDepthBits == 64, "fields must fill the key");

constexpr uint64_t fieldMask(int bits) { return (uint64_t{1} << bits) - 1; }

constexpr uint64_t packDrawKey(uint64_t renderPass,     // 0=shadow, 1=opaque, 2=transparent, 3=postfx
                               uint64_t shaderProgram,  // up to 1024 programs
                               uint64_t materialId,     // up to 16K materials
                               uint64_t meshId,         // up to 16K meshes
                               uint64_t depth)          // 24-bit quantized view depth: store it as-is for
                                                        // front-to-back, or fieldMask(24) - depth for back-to-front
{
  // Mask every field so an out-of-range id can't bleed into its neighbor.
  return ((renderPass    & fieldMask(kPassBits))     << (64 - kPassBits))
       | ((shaderProgram & fieldMask(kShaderBits))   << (kMaterialBits + kMeshBits + kDepthBits))
       | ((materialId    & fieldMask(kMaterialBits)) << (kMeshBits + kDepthBits))
       | ((meshId        & fieldMask(kMeshBits))     << kDepthBits)
       |  (depth         & fieldMask(kDepthBits));
}

// Sorting a std::vector<uint64_t> of these keys is one std::sort, or eight
// 8-bit LSD radix passes (fewer if the high bytes never vary).

The layout decides the draw order. With the render pass in the high bits, every draw in the same pass is contiguous after sorting; with depth in the low bits, draws that share a shader, material, and mesh come out front to back. Transparent draws are the exception: blending needs back-to-front order to outrank shader and material, so renderers either move the depth field above them for that pass (Ericson's approach^[2]) or sort the transparent pass with its own key. Either way, the sort routine only ever orders 64-bit integers.

14Galactic algorithms

An algorithm is galactic if its asymptotic behavior is excellent but its hidden constants are so large that it loses to an asymptotically worse algorithm on every input anyone would actually run, so it is never used to compute anything^[14]. The name comes from a 2010 post on Richard Lipton and Ken Regan's blog, which credits it to Regan.

The flagship example is matrix multiplication. The naive triple-loop algorithm is O(n³). Improvements to the exponent have kept coming since 1969 (a selection):

No entry past Strassen is used in practice. The Coppersmith-Winograd family would only overtake a cache-blocked cubic multiply on matrices far larger than any machine can hold, so the matrix products in graphics, audio, physics, and scientific libraries are O(n³) (occasionally Strassen at the top levels of very large products). Game engines mostly multiply 4×4 matrices, where none of this applies.

Galactic algorithms are still worth studying, for two reasons. First, they narrow the gap between what is achievable and the best general lower bound, which is still essentially the trivial Ω(n²) (every entry of the output has to be written). Second, techniques sometimes transfer down: Strassen's algorithm is practical, and it began the chain. For engineering purposes, "asymptotically faster" does not mean "faster on the inputs you have."

15NP-hard games

Big O can describe problems for which no polynomial-time algorithm is known, and which are believed to require exponential time. The class NP is the set of decision problems whose "yes" answers can be checked in polynomial time given a witness. The class P is the subset whose answers can also be computed in polynomial time. The P vs NP question is whether these are the same class.

A problem is NP-hard if every problem in NP reduces to it in polynomial time; NP-complete if it's both NP-hard and in NP. The Cook-Levin theorem (Cook 1971, Levin 1973 independently) showed that SAT is NP-complete, the first such proof^[22]; thousands of problems have since been shown NP-complete by chains of polynomial reductions that start from SAT.

Several games are known to be NP-hard in their generalized forms, and some are harder still:

These results apply to generalized versions (Tetris on an n × m board, Sudoku on n² × n²). The fixed-size game you play in your browser is solvable by brute force in principle; the asymptotic claim is about the family. The practical takeaway is that exact solvers for these problems can't be expected to scale, so game AI for them leans on heuristic search with aggressive pruning and on learned policies.

Procedural generation hits the same wall from the other side. Deciding whether an arbitrary Sokoban level is solvable is PSPACE-complete^[23]. Generators ship anyway: some build levels backward from a solved state by pulling boxes, so solvability holds by construction; others restrict the rules to a tractable subset, or run a solver with a bounded search budget and discard levels that don't certify within it.

16Beyond polynomial

Past exponential are growth rates so vast they have no operational meaning. The number of atoms in the observable universe is roughly 10⁸⁰; 2ⁿ crosses that threshold at n = 266, and n! crosses it at n = 59. The Ackermann function grows faster than any primitive-recursive function; already at A(4, 3) it produces a number far too large to write out in decimal^[27].

These aren't useful complexities for algorithms ("the algorithm runs in A(n, n) time" is functionally indistinguishable from "the algorithm doesn't terminate"), but they show up as inverse functions in tight upper bounds. The classic example: union-find with union-by-rank and path compression has an amortized cost per operation of O(α(n)), where α is the inverse Ackermann function; Tarjan proved the bound in 1975^[32]. For any n that fits in any computer ever built, α(n) ≤ 4, so in practice the operation is constant-time. Technically it is not constant: α grows without bound, just extraordinarily slowly.

17Try it yourself

The playground lets you pick one of six common data structures and one of four operations, then highlights the elements a single run of that operation touches next to its asymptotic cost.

18How engines actually use this

Asymptotic complexity drives many of the core data-structure choices in shipped engines, with constant-factor refinements layered on top. Concrete examples:

• Unreal Engine's TMap. A hash map whose elements live in a sparse array that tolerates gaps^[28]. It is built on TSet, whose hash buckets store element indices and chain colliding elements through a per-element "next" index (Set.h in the engine source). Average-case O(1) lookup, with the O(n) worst case showing up under pathological hash collisions; the dense element storage keeps iteration cheap.
• Unity's NativeParallelMultiHashMap. A Burst-compatible hash table that allows multiple values per key, a common building block for grid-based spatial partitioning in DOTS code. Average O(1) insert and lookup. Capacity is set up front, because its ParallelWriter cannot grow the table while several jobs write to it at once. (Older Collections versions called it NativeMultiHashMap.)
• Bevy ECS's archetype graph. Adding or removing a component changes an entity's archetype. Bevy caches, per archetype, an Edges table mapping each inserted or removed bundle to the destination archetype, so repeat transitions are a single lookup. Without it, every move would rebuild the entity's component list and hash it to find the target archetype, at a cost proportional to the number of components.
• Unreal's GPU particle sort. GPU-simulated translucent particles are depth-sorted on the GPU with a compute-shader radix sort (GPUSort.cpp and RadixSortShaders.usf in the engine source): O(d · n) work spread across thousands of GPU threads. The particle data already lives in GPU memory, so a CPU sort would add a readback and an upload every frame.
• Spatial hash for proximity queries. A uniform grid keyed on world-space cell coordinates, with each cell storing the list of objects whose AABB touches it, gives O(1) expected insert and O(k + 1) per query for k objects near the query point, as long as cells stay lightly occupied. The cell size has to be at least as large as the largest object's AABB to keep object-touches-cells at O(1). Teschner et al. 2003 analyze the cell-size and table-size tradeoffs for collision detection^[29].

The shared pattern: pick the asymptotic class first, then tune for cache and parallelism. Constant-factor work on an accidental O(n²) only moves the content size at which it breaks.

19Pitfalls

Mistakes that come up repeatedly in code review:

• Accidental quadratic from string concatenation. Building a string by repeated s = s + part costs O(n²) in the final length whenever each concatenation copies the whole accumulator, as it does for C++'s s = s + part and for immutable strings in Java and C#. Use s += part on a std::string, a string builder, or a join; all are amortized O(n). The same bug appears in tight loops building command buffers, log lines, or shader source.
• Linear search in a hot loop. "Find this asset by name" inside an inner loop turns a per-frame cost of O(1) into O(n), which compounds with anything wrapping it. Cache the lookup outside the loop or use a hash table.
• O(log n) in a tight loop is not "free." Logarithmic time gets treated as constant in casual analysis but adds up: a binary search per pixel at 1080p is 2 million searches per frame, and at 50 ns each (about 20 dependent probes, some of them cache misses) that is 100 ms, six 60 fps frames.
• Hash table worst case. A hash table is O(1) average and O(n) worst case. If your hash function is bad, the worst case is the actual case. For inputs an attacker controls (player-supplied names, network data), use a keyed hash such as SipHash, which Rust's HashMap uses by default, and check for long collision chains in QA builds.
• Treating amortized as worst-case. A vector push is O(1) amortized but O(n) on the resize. In a real-time loop, the resize is a hitch proportional to the vector's size, landing on whichever frame happens to trigger it. Pre-reserve when you know the size.
• Ignoring constants on small n. An n² algorithm with constant 1 beats an n log₂ n algorithm with constant 10 for every n up to 58. If the data structure is small and the operation is hot, the asymptotically better algorithm can be the wrong choice.
• Vector copy in a hot loop. Passing a std::vector by value copies it: O(n) per call. The signature looks innocuous; the copy isn't. Pass by const-reference unless you actually need the copy.
• Recursive complexity miscounted. A recursion that branches twice per level costs O(2^depth), not O(depth). Naive recursive Fibonacci is the textbook case (about 1.6ⁿ calls); memoization brings it to O(n).

20What's next

The natural follow-ups are the algorithms whose complexity this tutorial only sketched:

• Sorting and searching deep-dives. Why introsort, why radix, why pdqsort, why timsort; the sorting tutorial covers each. The O(n log n) family is more crowded than it looks.
• The external-memory and cache-oblivious models. Big O over block transfers instead of CPU operations. Sorting N items with a cache of size M and blocks of size B needs Θ((N/B) · log_M/B(N/B)) transfers^[31], and Frigo et al.'s funnelsort reaches that bound without knowing M or B (assuming the cache is "tall": M at least about B²)^[13]. It is the model to reach for when the data is much larger than cache.
• Parallel algorithms. The work-span model popularized by Cilk, and the older PRAM model. The job systems tutorial introduces the runtime; the complexity model for analyzing parallel algorithms is a tutorial of its own.
• NP-hard heuristics. If a problem is NP-hard, exact solutions at scale are out; approximation algorithms (including PTAS and FPTAS), local search, and learned heuristics are the practical answers. Multi-agent pathfinding and much of the game-AI planning literature live here.
• Lower bounds. When you've shown an algorithm runs in O(f(n)), the next question is whether any algorithm can do better. Information-theoretic lower bounds, comparison-tree lower bounds, and circuit-complexity lower bounds answer this, and they are usually much harder to prove than upper bounds.

The most useful next step is empirical: profile at shipping content scale, look for costs that grow faster than the content does, and replace the ones that will actually see large n.

Sources

1. Matt Pharr, Wenzel Jakob, Greg Humphreys. Physically Based Rendering: From Theory to Implementation, 3rd ed., 2018, §4.3 "Bounding Volume Hierarchies." pbr-book.org. BVH construction with the surface-area heuristic, and BVH traversal.
2. Christer Ericson. "Order your graphics draw calls around!" realtimecollisiondetection.net, October 2008. realtimecollisiondetection.net. The widely cited write-up of bit-packed draw-call sort keys, including swapping the depth and material fields for translucent draws.
3. Erik D. Demaine, Susan Hohenberger, David Liben-Nowell. "Tetris is Hard, Even to Approximate." COCOON 2003. arXiv:cs/0210020. Original NP-completeness proof for generalized Tetris.
4. Jonathan D. Cohen, Ming C. Lin, Dinesh Manocha, Madhav K. Ponamgi. "I-COLLIDE: An Interactive and Exact Collision Detection System for Large-Scale Environments." Proc. ACM Interactive 3D Graphics, 1995. The standard reference for sweep-and-prune (sort-and-sweep) with incremental re-sorting that exploits frame-to-frame coherence.
5. Scott Le Grand. "Broad-Phase Collision Detection with CUDA." GPU Gems 3, ch. 32, NVIDIA, 2007. developer.nvidia.com. A uniform-grid broad phase on the GPU: cells at least as large as the largest object, a parallel radix sort of cell IDs, and multi-pass processing of cell types so no pair is tested twice.
6. Erik R. Tou. "Math Origins: Orders of Growth." MAA Convergence, January 2018. archived copy (the old.maa.org site is offline). Historical survey covering du Bois-Reymond's 1877 infinitary calculus, Bachmann 1894, Landau 1909, and Hardy 1910.
7. Paul Bachmann. Die analytische Zahlentheorie, vol. II, Teubner, 1894. archive.org scan. First published use of the O symbol, in the chapter on divisor functions; "O" is usually read as "Ordnung."
8. Edmund Landau. Handbuch der Lehre von der Verteilung der Primzahlen, Teubner, 1909. archive.org scan. Introduces the little-o notation; the source of "Landau symbols."
9. G. H. Hardy, J. E. Littlewood. "Some Problems of Diophantine Approximation: Part II. The Trigonometrical Series Associated with the Elliptic θ-Functions." Acta Mathematica 37, 1914. Introduces the original Ω notation as a non-vanishing-remainder marker; predates Knuth's stricter algorithmic Ω.
10. Donald E. Knuth. "Big Omicron and Big Omega and Big Theta." ACM SIGACT News 8(2):18–24, 1976. dl.acm.org. The standardization paper for algorithm analysis: defines Big O, Big Ω, Big Θ as used today.
11. Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein. Introduction to Algorithms, 4th ed., MIT Press, 2022, ch. 3–4 and §8.1. The textbook reference for asymptotic notation, the master theorem (with Akra-Bazzi in §4.7), and the comparison-sort lower bound.
12. David R. Musser. "Introspective Sorting and Selection Algorithms." Software: Practice and Experience 27(8):983–993, 1997. PDF. The introsort design (quicksort with a depth-limited heapsort fallback and a final insertion-sort pass) that libstdc++, libc++, and MSVC's std::sort build on.
13. Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran. "Cache-Oblivious Algorithms." Proc. 40th IEEE FOCS, 1999. PDF. The original cache-oblivious paper: the ideal-cache model and algorithms (including funnelsort) that meet the optimal transfer bounds without knowing the cache parameters.
14. Richard J. Lipton, Kenneth W. Regan. "Galactic Algorithms." Gödel's Lost Letter and P=NP, 23 October 2010. rjlipton.com. The post that introduced the name, credited to Regan, for algorithms that are wonderful asymptotically but never used to compute anything. Discusses Coppersmith-Winograd matrix multiplication.
15. Peter Norvig. "Teach Yourself Programming in Ten Years," "Approximate timing for various operations" table. norvig.com/21-days.html. Memory-hierarchy latency ballpark numbers (L1 ~0.5 ns, L2 ~7 ns, DRAM ~100 ns).
16. Agner Fog. "The microarchitecture of Intel, AMD and VIA CPUs," chapter on branch prediction. PDF. Source for the 15–20 cycle branch-misprediction penalty on modern x86 cores.
17. Robert E. Tarjan. "Amortized Computational Complexity." SIAM Journal on Algebraic Discrete Methods 6(2):306–318, 1985. Formalizes amortized analysis (the banker's and physicist's views).
18. Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, Renfei Zhou. "New Bounds for Matrix Multiplication: from Alpha to Omega." Proc. SODA 2024 (arXiv:2307.07970); result ω < 2.371552. Subsequently improved by Josh Alman, Ran Duan, and the same group in "More Asymmetry Yields Faster Matrix Multiplication," Proc. SODA 2025 (arXiv:2404.16349), to ω < 2.371339. Currently the best published exponents. arXiv 2307.07970, arXiv 2404.16349.
19. NVIDIA. "NVIDIA Turing GPU Architecture Whitepaper," 2018, "RT Core" section. PDF. Hardware-accelerated BVH traversal in fixed-function silicon.
20. Peter E. Hart, Nils J. Nilsson, Bertram Raphael. "A Formal Basis for the Heuristic Determination of Minimum Cost Paths." IEEE Transactions on Systems Science and Cybernetics 4(2):100–107, 1968. Original A* paper; the optimality result under admissible heuristics.
21. Bevy Engine. "Use radix sort for sort phase and sprite sorting." GitHub issue #4291, 2022. github.com. Benchmarks of the radsort crate against Rust's comparison sorts for Bevy's render-phase sorts: 0.728 ms to 0.094 ms on many_cubes, but roughly 10× slower on two sprite benchmarks. Bevy 0.8 shipped radsort for its 3D phase sorts; later releases moved opaque meshes to unsorted bins and sort transparent phases with Rust's stable comparison sort, and radsort remains in sprite picking.
22. Stephen A. Cook. "The Complexity of Theorem-Proving Procedures." Proc. ACM STOC, 1971, pp. 151–158. dl.acm.org. The original NP-completeness theorem; SAT is NP-complete. Leonid Levin proved an equivalent result independently in "Universal Sequential Search Problems," Problemy Peredachi Informatsii 9(3):115–116, 1973 (English translation: Problems of Information Transmission 9:265–266), hence the joint Cook-Levin name.
23. Joseph Culberson. "Sokoban is PSPACE-complete." Technical Report TR97-02, University of Alberta, 1997; also in Proc. Fun with Algorithms, 1998. archived copy. PSPACE-completeness proof for generalized Sokoban.
24. Greg Aloupis, Erik D. Demaine, Alan Guo, Giovanni Viglietta. "Classic Nintendo Games are (Computationally) Hard." Theoretical Computer Science 586:135–160, 2015. NP-hardness proofs for generalized Super Mario Bros, Donkey Kong, Legend of Zelda, Metroid, and Pokémon.
25. Richard Kaye. "Minesweeper is NP-Complete." The Mathematical Intelligencer 22(2):9–15, 2000. NP-completeness proof for the Minesweeper Consistency Problem.
26. Takayuki Yato, Takahiro Seta. "Complexity and Completeness of Finding Another Solution and Its Application to Puzzles." IEICE Transactions E86-A(5):1052–1060, 2003. NP-completeness proof for generalized n²×n² Sudoku.
27. Wilhelm Ackermann. "Zum Hilbertschen Aufbau der reellen Zahlen." Mathematische Annalen 99:118–133, 1928. Original Ackermann function (later simplified by Péter and Robinson to the two-argument form used today).
28. Epic Games. "TMap Reference," Unreal Engine 5 documentation. dev.epicgames.com. Documentation of Unreal's hash-map data structure and its design choices.
29. Matthias Teschner, Bruno Heidelberger, Matthias Müller, Danat Pomeranets, Markus Gross. "Optimized Spatial Hashing for Collision Detection of Deformable Objects." Proc. Vision, Modeling, Visualization (VMV) 2003. PDF. Cell-size analysis for uniform spatial hashing applied to collision detection; the canonical reference on the tradeoff between query cost and per-cell occupancy.
30. NVIDIA. "Rigid Body Collision," PhysX 5.4.0 SDK documentation, Broad-phase section. nvidia-omniverse.github.io. Names the available broad-phase algorithms (eSAP, eMBP, eABP, ePABP, eGPU) and calls eABP "a good default choice for the broadphase."
31. Alok Aggarwal, Jeffrey Scott Vitter. "The Input/Output Complexity of Sorting and Related Problems." Communications of the ACM 31(9):1116–1127, 1988. doi.org/10.1145/48529.48535. The external-memory model that counts block transfers, and the Θ((N/B) log_M/B(N/B)) transfer bound for sorting.
32. Robert E. Tarjan. "Efficiency of a Good But Not Linear Set Union Algorithm." Journal of the ACM 22(2):215–225, 1975. doi.org/10.1145/321879.321884. Proves the inverse-Ackermann bound for union-find with path compression and union by rank.