Big O Notation
A system that runs fine on a test scene with a hundred objects can eat the whole frame on a shipping level with ten thousand. Big O is how you see that coming from the code, before a profiler or a QA report shows it: it tells you how a function's cost grows as its input grows. This page teaches you to read and use it, then applies it to four engine problems (broad-phase collision, BVH ray traversal, A* pathfinding, draw-call sorting), with a live demo for each idea.
- Look at a loop nest and say how its cost grows when the input doubles, and estimate what that means in milliseconds at shipping content sizes.
- Read O, Ω and Θ claims in papers and docs and know which direction each one promises.
- Spot accidental quadratic code in review, and know when a "worse" algorithm is the right call because your n stays small.
- Tell worst-case, average and amortized cost apart, and know which one causes frame hitches.
- Work out the cost of a recursive algorithm such as merge sort or a BVH build, and measure the growth rate of code you can't analyze by hand.
01Why a notation, not a stopwatch
Physics has to find which objects might be touching. The simplest way is two nested loops: for every pair of objects, test whether their boxes overlap. On a test scene with four objects that's six tests, and nobody ever profiles it. On a shipping scene with 800 objects it's 319,600 tests, every frame. Timing the function on day one tells you nothing about that. What does tell you is noticing that the number of tests grows with the square of the object count.
Worked example
Pairs of n objects: n × (n − 1) / 2. Say one box test costs 5 ns.
4 objects: 6 tests, 30 ns. 800 objects: 319,600 tests, 1.6 ms, about a tenth of a 16.7 ms frame (60 fps). 5,000 objects: 12.5 million tests, 62 ms, almost four whole frames.
Going from 800 to 5,000 objects is 6.25× more content, but 39× more work.
is the shorthand for that growth. You keep only the term that grows fastest and drop the constant multipliers, the smaller terms and the hardware. The pair test above does n(n − 1)/2 = n²/2 − n/2 tests, so you call it O(n²), "order n squared". What's left is the shape of the cost curve, and the shape is what decides whether a system survives the jump from test scene to shipping content. It doesn't depend on the CPU: a faster machine moves the curve down, but it doesn't change how steeply it climbs.
Three ways to find touching pairs
Faster methods exist, and §10 explains how they work. The widget below compares 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), where k is the number of pairs that really do overlap. Drag the scene-size slider and watch the gap open up:
02Where the notation came from
You'll read Big O in papers, library docs and code review comments, and two quirks of its history explain things that otherwise look odd. Paul Bachmann introduced it in 1894 to bound error terms in number theory[7], and they wrote f(n) = O(g(n)) with an equals sign even though it means "is at most", which is why you'll also see f ∈ O(g). And the Ω symbol means something weaker in older math papers than in computer science, where Knuth fixed today's definitions in 1976[10].
In engine work, Big O is usually the first filter: it catches a quadratic before it ships. Then cache behavior, branch prediction and SIMD (instructions that process 4 to 16 values at once) decide between the candidates that pass it. §6 covers the cache and branch costs.
Timeline: from number theory to algorithm analysis
03The definition, picked apart
A reviewer writes "this is O(n²)" on your pull request. What exactly are they promising? Not a time, and not even an operation count. The claim is: past some input size, the cost never exceeds some fixed multiple of n². You get to pick both the multiple and the size where the promise starts. That freedom is what lets Big O ignore constants and small terms.
Worked example
A function does f(n) = 3n² + 12n + 50 operations. Is it O(n²)?
Try the multiple 4: you need 3n² + 12n + 50 ≤ 4n², which is n² ≥ 12n + 50. At n = 15 it fails: f(15) = 905, but 4 × 225 = 900. At n = 16 it holds: f(16) = 1,010 and 4 × 256 = 1,024. From there on n² grows faster than 12n + 50, so it keeps holding.
So the multiple 4 works from n = 16 onward, and f is O(n²). A bigger multiple starts earlier: with 5, it holds from n = 9 (f(9) = 401 ≤ 405).
That multiple is called c and the starting size is called n₀. The formal statement is the same check written for every n, the way Knuth wrote it[10] and the CLRS textbook teaches it[11]:
In words: f(n) is O(g(n)) if you can find some multiple c and some starting size n₀ so that, for every input at least that big, f(n) is at most c times g(n). The c is what lets you throw away constant factors, and the n₀ is what lets you throw away the smaller terms. Any one pair that works is enough.
Three things the definition does not say matter as much as what it does say:
- The "=" isn't equality. Read "f = O(g)" as "f is O(g)". O(g) is really the set of all functions that grow no faster than g, so f ∈ O(g) is the more precise spelling. The "=" survives because that's how Bachmann wrote it.
- It's only a ceiling. Big O is an upper bound. f(n) = O(n²) is true if f grows like n², but also if it grows like n, or n log n, or anything slower. "Linear search is O(n²)" is technically true and almost always misleading.
- It says nothing about small inputs. An O(n) algorithm can be slower than an O(n²) one on every input you ever give it, if the quadratic one has a small enough constant. Insertion sort beats quicksort below a few dozen elements, which is why most production sorts switch to insertion sort for small ranges (libstdc++ at 16 elements, MSVC at 32)[12].
The widget below runs the worked example's check for you. The orange curve is f(n), the violet curve is c × g(n), and the vertical line is n₀. The bound holds when orange stays under violet everywhere to the right of the line:
Why do you get to pick n₀?
The point of n₀ is to let you ignore noise at small n. A function might do weird things for the first ten or hundred inputs (a startup cost, a one-time table fill, a cache that hasn't warmed up) and then settle into its real growth shape. Big O cares about the real growth shape, not the noise.
Choosing n₀ = 0 is a stronger claim ("the bound holds for every input"); choosing n₀ = 106 is a weaker one ("the bound holds from a million on"). The definition only asks you to find some n₀, which ignores small-input artifacts without giving up the bound. The flip side: a large n₀ is a warning sign that the bound may not describe the sizes you actually run.
04Omega, Theta, and the rest of the family
Two claims you'll meet: "std::sort is O(n log n)" in a library's docs, and "no comparison sort can beat n log n" in a textbook. The first is a ceiling on one algorithm. The second is a floor under every possible algorithm for the problem. Big O only writes ceilings, so you need a symbol for floors, Ω (Omega), and one for "both at once", Θ (Theta).
Worked example
f(n) = 3n² + 5n.
Floor: f(n) ≥ 3n² for every n ≥ 0, so f is Ω(n²) with c = 3.
Ceiling: 5n ≤ n² once n ≥ 5, so f(n) ≤ 4n² from n = 5 on (f(5) = 100 = 4 × 25; at n = 4, f = 68 is more than 64). So f is O(n²) with c = 4.
Both hold, so f is Θ(n²): it grows like n², no faster and no slower.
The full family has five members. Each is one flipped inequality away from the others:
| Name | Symbol | Meaning | Definition | Reads as |
|---|---|---|---|---|
| Big O | O(g) | Upper bound (not necessarily tight) | ∃c, n₀ ∀n≥n₀: f ≤ c·g | "grows no faster than" |
| Big Omega | Ω(g) | Lower bound (not necessarily tight) | ∃c, n₀ ∀n≥n₀: f ≥ c·g | "grows no slower than" |
| Big Theta | Θ(g) | Tight bound, same growth | f = O(g) and f = Ω(g) | "grows exactly like" |
| Little o | o(g) | Strictly slower | ∀c > 0 ∃n₀ ∀n≥n₀: f < c·g | "grows strictly slower than" |
| Little omega | ω(g) | Strictly faster | ∀c > 0 ∃n₀ ∀n≥n₀: f > c·g | "grows strictly faster than" |
The "little" versions are stricter. Big O needs one multiple c that works. Little o needs every positive c, however small, to work eventually. So f can't just stay within a constant factor of g: it has to fall further and further behind.
A single function fits several of these at once, which is why the tightest one is the useful one to state:
In words: 3n² + 5n grows no faster than n², exactly like n², no slower than n, strictly slower than n³ and strictly faster than n. All five are true. Θ(n²) is the one that pins it down; the others leave room. Likewise "merge sort is Θ(n log n)" says more than "merge sort is O(n log n)", because it also rules out merge sort ever running faster than n log n.
When you'd actually write little o
Little o claims one function grows fundamentally slower than another, which is stronger than being smaller by some constant factor. 1/n = o(1) says 1/n shrinks to zero. n log n = o(n²) says no constant multiple of n log n keeps up with n²: the gap grows without bound. You'll mostly see it in papers that state error terms or compare growth rates precisely.
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. Read O() that way unless the author explicitly separates the two.
Algorithm analysis usually wants Θ (matching upper and lower bounds) for the algorithm you wrote, and Ω for the problem you're solving (the best possible algorithm). "Merge sort is O(n log n)" and "comparison-based sorting is Ω(n log n)" combine to say "merge sort is worst-case optimal among comparison sorts, up to a constant factor."
05The growth zoo, racing
A designer asks whether the next level can have ten times as many NPCs. If the AI update is O(n), it costs about ten times as much. If it's O(n²), it costs about a hundred times as much. If it's O(log n), you'll barely notice. Knowing the common classes by sight gives you that answer in seconds, before anyone builds the level.
Worked example
Some code takes 2 ms with 1,000 NPCs. Estimate 10,000 NPCs:
O(n): 2 ms × 10 = 20 ms. O(n log n): 2 ms × 10 × (log 10,000 / log 1,000) = 2 × 10 × 4/3 ≈ 27 ms. O(n²): 2 ms × 100 = 200 ms.
Only the linear version is even close to a 16.7 ms frame, and it's already over.
A handful of classes cover most of the algorithms an engine programmer meets. The last column assumes each basic step takes 1 ns:
| Class | Name | Where you'll see it | At n=106 (1 ns/op) |
|---|---|---|---|
| O(1) | Constant | Hash table lookup (average), array index, push to a stack | 1 ns |
| O(log n) | Logarithmic | Binary search, balanced BST operation, typical BVH ray query | 20 ns |
| O(√n) | Square-root | Trial-division primality test, sqrt decomposition | 1 µs |
| O(n) | Linear | Linear search, single pass over an array, building a histogram | 1 ms |
| O(n log n) | Linearithmic | Comparison-based sort, FFT, sweep-and-prune broad phase | 20 ms |
| O(n²) | Quadratic | Nested-loop pair test, bubble sort, naive matrix-vector product | 17 min |
| O(n³) | Cubic | Naive matrix multiply, Floyd-Warshall all-pairs shortest paths | 32 years |
| O(2n) | Exponential | Brute-force SAT over n variables, subset enumeration | ≫ age of universe |
| O(n!) | Factorial | Brute-force TSP, permutation enumeration | ≫≫ age of universe |
At a million elements, O(n) takes a millisecond, O(n²) a quarter of an hour and O(n³) three decades. Each step up the table is a factor of a million at this size, and no amount of tuning closes a gap like that.
The widget below draws them on a log-log plot: both axes go up by a factor of ten per gridline, so huge and tiny values fit on one chart. On those axes nk becomes a straight line with slope k (n² climbs twice as steeply as n), which makes growth rates easy to compare by eye:
06When constants lie
An inventory holds a few dozen items. You could find one with a linear scan of a flat array, O(n), or with a balanced tree, O(log n). At that size the scan often wins: it streams through contiguous memory, while the tree chases pointers and can miss cache on every hop. Big O drops constants on purpose, so it can compare algorithms across hardware and compilers. The price is that an algorithm with a worse Big O can beat one with a better Big O on every input you'll actually see.
To find where the "better" algorithm starts winning, set the two costs equal. Take a linear algorithm costing 100n and a quadratic one costing n² / 100:
In words: the two costs are equal at n = 10,000. Below that, the quadratic algorithm is cheaper; above it, the linear one is. A system that never exceeds 10,000 elements is better off with the "worse" algorithm.
Worked example
At n = 1,000: linear costs 100 × 1,000 = 100,000; quadratic costs 1,000² / 100 = 10,000. The quadratic one is 10× cheaper.
At n = 100,000: linear costs 10 million; quadratic costs 100 million. Now the linear one is 10× cheaper, and the gap keeps widening.
What constants stand for in practice
The hidden constant is everything a single step really costs on the machine. Three common reasons it's large:
- 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
malloconce 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.
An algorithm with hidden constant 106 is in the same Big O class as one with hidden constant 1, and a million times slower at every n. The Coppersmith-Winograd matrix-multiply algorithm hides a constant so large that it would only win on matrices far too big for any computer; no shipping linear-algebra library uses it[14]. Big O says nothing about the size of the constant.
07Worst, best, average, amortized
Your game runs at a steady 60 fps, except for one frame every few seconds that takes 30 ms. The average cost per frame is fine; one particular call is not. That's the difference between the cost averaged over many calls and the cost of the worst single call, and Big O can describe either. Two inputs of the same size can also cost very different amounts. So a Big O claim about an algorithm has to say which cost it means:
- Worst case: the cost on the slowest input of size n. This is the default. When the literature says "quicksort is O(n²)", it means the worst case.
- Best case: the cost on the fastest input. Usually less interesting, but insertion sort's best case is Θ(n) on already-sorted input, which matters when your data arrives nearly sorted.
- Average case: the expected cost when inputs follow some assumed distribution. Quicksort averages Θ(n log n) when every input order is equally likely. Useful, but only as good as that assumption about your input.
- Amortized: the average cost per operation over a long sequence of operations. std::vector::push_back is O(1) amortized even though a single push costs O(n) when the vector has to grow. That one expensive push is your 30 ms frame.
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 pivot is always the smallest (or largest) value left, so each pass peels off just one element.
Worked example
Sort [1, 2, 3, 4, 5] using the first element as the pivot.
Pivot 1: compare it with the 4 others, all bigger. Left side empty, right side [2, 3, 4, 5]. Pivot 2: 3 comparisons. Then 2, then 1.
Total: 4 + 3 + 2 + 1 = 10 = 5 × 4 / 2. In general n(n − 1)/2, which is Θ(n²). A random order of the same five values usually splits nearer the middle and needs fewer.
The widget runs a first-element-pivot quicksort on three input patterns and counts its comparisons:
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).
Worked example
Push 8 items into a vector that starts with room for 1 and doubles when full. Count one unit per element written or copied.
Push 1: 1. Push 2: full, copy 1 then write, 2. Push 3: copy 2, write, 3. Push 4: 1. Push 5: copy 4, write, 5. Pushes 6 to 8: 1 each.
Total: 1 + 2 + 3 + 1 + 5 + 1 + 1 + 1 = 15, or about 1.9 per push, even though one push cost 5.
The general argument just adds things up (the "aggregate method" from the amortized-analysis framework Tarjan formalized in 1985[17]). n pushes do n writes plus the resize copies, which have sizes 1, 2, 4, and so on, doubling, each smaller than n. A doubling series like that adds up to less than twice its largest term, so the copies total less than 2n. All the work is less than 3n, so the cost per push is at most 3: O(1).
08The Master Theorem
You're writing a BVH builder: split the objects in two, build each half the same way, and do some work at each split to choose where to cut. How does the total cost grow? Loops you can count by eye, but recursion hides the count. Algorithms built this way, by splitting a problem into smaller copies of itself, solving those and combining the answers, are called divide-and-conquer, and there's a shortcut for their cost.
The intuition is to draw the recursion as a tree and add up the work level by level. If every level does about the same work, the total is that work times the number of levels.
Worked example
Merge sort on 8 elements: split into two halves of 4, sort each half, then merge them, which touches all 8 elements.
Level 1: one merge of 8 elements, 8 work. Level 2: two merges of 4, 8 work. Level 3: four merges of 2, 8 work. That's 3 levels of 8.
Total: 3 × 8 = 24 = 8 × log₂ 8. In general n per level times log₂ n levels: Θ(n log n).
To use the shortcut, first write the cost as a recurrence: an equation that gives the cost on n items in terms of the cost on smaller pieces. Most divide-and-conquer algorithms fit this form:
In words: to solve a problem of size n, solve a smaller problems, each of size n/b, plus f(n) work at this level to split or combine. 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] (you'll meet the name in textbooks and interviews) answers the recurrence by comparing two things: how fast the number of pieces multiplies going down the tree, and how fast the work per piece shrinks. One number captures the first, ccrit = logb a. For merge sort, log₂ 2 = 1. Compare it with the exponent of f(n) and one of three cases applies:
- Case 1: leaves dominate. If f(n) = O(nc) with c < ccrit, then T(n) = Θ(nccrit). The recursion tree has so many leaves that they outweigh the combine work.
- Case 2: every level costs the same. If f(n) = Θ(nccrit), then T(n) = Θ(nccrit log n). Each of the logb n levels does the same amount of work. Merge sort lives here: ccrit = 1, f(n) = Θ(n), total Θ(n log n).
- Case 3: root dominates. If f(n) = Ω(nc) with c > ccrit, and a regularity condition holds, then T(n) = Θ(f(n)). The top-level combine work is so expensive that the recursion contributes nothing significant.
Six recurrences, solved
Six standard divide-and-conquer recurrences and what the theorem says about them. In the binary search row the work per level is constant, which is n0, and ccrit = log₂ 1 = 0, so case 2 applies:
| Algorithm | Recurrence | ccrit | Case | Result |
|---|---|---|---|---|
| Binary search | T(n) = T(n/2) + Θ(1) | 0 | Case 2 (c=0) | Θ(log n) |
| Merge sort | T(n) = 2T(n/2) + Θ(n) | 1 | Case 2 | Θ(n log n) |
| Karatsuba multiplication | T(n) = 3T(n/2) + Θ(n) | log₂3 ≈ 1.585 | Case 1 | Θ(nlog₂3) ≈ Θ(n1.585) |
| Strassen matrix multiply | T(n) = 7T(n/2) + Θ(n²) | log₂7 ≈ 2.807 | Case 1 | Θ(nlog₂7) ≈ Θ(n2.807) |
| Naive matrix multiply (recursive) | T(n) = 8T(n/2) + Θ(n²) | 3 | Case 1 | Θ(n³) |
| BVH top-down (binned SAH, balanced splits) | T(n) = 2T(n/2) + Θ(n) | 1 | Case 2 | Θ(n log n) |
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).
The cases that aren't in the Master Theorem
The classical Master Theorem doesn't cover every recurrence. Three gaps:
- Logs in f(n). If f(n) = Θ(nccrit logk n), the three cases above don't apply. An extended case 2 gives Θ(nccrit logk+1 n), and the Akra-Bazzi method covers it too.
- Uneven splits. T(n) = T(n/5) + T(7n/10) + O(n) (median-of-medians selection) requires Akra-Bazzi or direct analysis; it solves to Θ(n).
- Subtractive recurrences. T(n) = T(n-1) + O(n) (quicksort worst case, naive recursion) isn't divide-and-conquer; it's "shrink by 1." The answer is the sum Θ(n²), found by direct summation.
For the recurrences this tutorial cares about, the three-case Master Theorem above is sufficient. The Akra-Bazzi version is in CLRS chapter 4[11].
09Measuring growth empirically
The pathfinder got slow on the new level, and it calls into three libraries you didn't write. You can't count its loops, but you can time it. Run it at a few sizes, each double the last, and see how the time grows. That tells you the class without reading a line of the code.
The quickest test is the doubling ratio: time it at n and at 2n and divide. Doubling n doubles an O(n) cost and quadruples an O(n²) one.
Worked example
You measure 2.0 ms at 1,000 nodes and 8.1 ms at 2,000.
Ratio: 8.1 / 2.0 ≈ 4.05, so it's quadratic. The exponent is log₂ 4.05 ≈ 2.02.
Prediction: 4,000 nodes should take about 32 ms. If it takes 16 ms instead, the earlier ratio was noise and the code is linear.
The same idea works on a whole set of timings with a log-log plot. If T(n) = c · nk, then log T = log c + k · log n: a straight line whose slope is the exponent k. A slope of 1 means O(n) and a slope of 2 means O(n²). Anything between 1 and 2 is ambiguous: it could be O(n log n), could be O(n1.5), and the slope alone can't tell them apart.
Here's how the doubling ratio reads for each class:
| Doubling ratio | Diagnosis | Slope on log-log |
|---|---|---|
| ~1 | O(1) | 0 |
| ~1 + 1/log n | O(log n) | tends to 0 |
| ~2 | O(n) | 1 |
| ~2.1–2.3 | O(n log n) | slightly above 1 |
| ~4 | O(n²) | 2 |
| ~8 | O(n³) | 3 |
The widget below plots a simulated set of timings and lets you guess the class. The points carry up to ±9% random noise, standing in for the cache effects, GC pauses and scheduler hiccups of real measurements, so the readouts won't land exactly on the table's values.
10Case study: broad-phase collision
Broad-phase collision is the classic engine-side O(n²) trap. Before physics works out exact contacts, it needs a cheap first pass, the broad phase, that finds every pair of objects whose bounding boxes 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)
Two boxes can only overlap if their extents overlap on the X axis, so start there. Sort the bounding-box endpoints along X. Two boxes overlap on X unless one ends before the other starts. 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 mostly the initial sort, O(n log n). The sweep itself is O(n + k), where k is the number of pairs found active together. 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
Divide space into a regular grid. Record each object in every cell its AABB touches, using a hash table keyed by cell coordinates so empty cells cost nothing. Two objects can only collide if they share a cell, so you only test pairs within each cell. Building the grid is O(n); the tests cost whatever the cells' pair counts add up to.
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.
Worked example
1,000 objects, about 2 per cell, so roughly 500 occupied cells.
Brute force: 1,000 × 999 / 2 = 499,500 tests. Hash: 500 cells × 1 pair each = 500 tests, plus 1,000 insertions, about 1,500 operations, over 300× fewer.
Now pile all 1,000 into 10 cells, 100 each: 10 × (100 × 99 / 2) = 49,500 tests. Still 10× better than brute force, but about 100× more pair tests than the spread-out scene.
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 work counts are close, and brute force's tiny per-test cost can make it the fastest in wall-clock terms. At high counts it loses by a wide margin:
11Case study: BVH ray traversal
A renderer wants to know what a reflection ray hits. By brute force, that means testing the ray against every triangle in the scene: O(n) per ray, and O(n × pixels) for one ray per pixel. At 107 triangles and a 1080p image (about 2 million pixels) that's 2×1013 ray-triangle tests per frame, far more than any real-time renderer can afford.
A 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.
Worked example
1 million triangles, at most 4 per leaf, in a balanced binary tree: 250,000 leaves, so log₂ 250,000 ≈ 18 levels.
A ray that only ever goes down one path tests 2 child boxes per level and 4 triangles at the leaf: about 2 × 18 + 4 = 40 tests instead of 1,000,000. Real rays often have to try more than one path, so the count is some multiple of that, and it grows with the depth of the tree, about log₂ of the triangle count.
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
An enemy needs a path to the player across a level full of walls. A* is the usual search for that. It keeps a frontier, the set of cells it has reached but not yet explored from, and always explores next the one that looks cheapest overall: the known cost to get there, g, plus a guess at the cost still to go, h (the heuristic). For a node x, that score is f(x) = g(x) + h(x).
Worked example
Open grid, moves in four directions, each costing 1. Start at (0, 0), goal at (6, 3). Use the Manhattan distance as the guess: h = |dx| + |dy|.
Step right to (1, 0): g = 1, h = 5 + 3 = 8, so f = 9. Step left to (−1, 0): g = 1, h = 7 + 3 = 10, so f = 11.
A* explores the right-hand cell first, and on an open map it never needs the left one. A search with no guess (h = 0) scores both at 1 and explores in every direction.
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.
How much does that save? The textbook worst case for A* as a tree search, one that doesn't remember where it has been, is O(bd), 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 (polygons covering the walkable floor) 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 450 nodes; with a visited set, BFS expands at most the grid's n = 104 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. If consecutive calls use different shaders or materials, the GPU has to switch state between them, and each switch costs CPU time in the driver and can stall the GPU. Reordering the calls so that ones sharing a render target, shader or material sit together cuts the number of switches[2]. That reordering is a sort, run every frame, so its Big O shows up in the frame time.
A common pattern: every draw call gets a 32- or 64-bit integer sort key that packs render pass, shader, material, depth and so on into bit fields, most important field in the highest bits. Sort the keys as plain integers and issue the calls in that order.
Worked example
Using the layout in the listing below: draw A is opaque (pass 1) with shader 5, material 300, depth 1,000. Draw B is opaque with shader 7, material 2, depth 10.
Both keys have the same pass bits. The next field down is the shader, and 5 < 7, so A's key is smaller and A draws first, whatever the material and depth fields hold. Depth only breaks ties between draws that match on every field above it.
Cost for 10,000 draws: a comparison sort does about n log₂ n ≈ 133,000 comparisons; an 8-pass radix sort (below) moves each key once per pass, 80,000 moves, plus a 256-entry count table per pass.
Two ways to do the sort:
- 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::sortfor small ranges.
Why isn't every sort a radix sort? 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):
| Year | Author(s) | Exponent ω | Practical? |
|---|---|---|---|
| 1969 | Strassen | log₂7 ≈ 2.807 | Sometimes, for large matrices |
| 1978 | Pan | 2.795 | No; constants too large |
| 1981 | Schönhage | 2.522 | No |
| 1990 | Coppersmith-Winograd | 2.376 | No; canonical galactic algorithm |
| 2014 | Le Gall | 2.3728639 | No |
| 2024 | Vassilevska Williams, Y. Xu, Z. Xu, Zhou[18] | 2.371552 | No |
| 2025 | Alman, Duan, Vassilevska Williams, Y. Xu, Z. Xu, Zhou[18] | 2.371339 | No |
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
You're building a puzzle generator and want a solver that checks every generated level is solvable before it ships. For some puzzle families, nobody knows a solver whose cost grows polynomially (like n², n³ or any fixed power of the level size), and most researchers believe none exists. Knowing that before you start saves you from trying to optimize your way out of it.
The vocabulary: a yes-or-no problem is in NP if, when the answer is yes, someone can hand you evidence (say, a solution) that you can check in polynomial time. It's in P if you can also find the answer in polynomial time. Whether every problem in NP is also in P is the open P vs NP question.
A problem is NP-hard if a fast solver for it would give you a fast solver for every problem in NP: each of them can be translated into it in polynomial time. It's NP-complete if it's NP-hard and also in NP. So a polynomial-time algorithm for any NP-complete problem would prove P = NP, which is why "this is NP-complete" is read as "don't expect a fast exact solver".
Where NP-completeness starts
The Cook-Levin theorem (Cook 1971, Levin 1973 independently) proved that SAT, the problem of whether a true/false formula can be made true, is NP-complete, the first such proof[22]. Thousands of problems have since been shown NP-complete by chains of polynomial-time translations that start from SAT.
Several games are NP-hard once generalized to boards of any size, and some are harder still:
| Game | Problem statement | Complexity | Reference |
|---|---|---|---|
| Generalized Tetris | Maximize survival on a known sequence of pieces | NP-complete | [3] |
| Sokoban | Push boxes onto target tiles | PSPACE-complete | [23] |
| Super Mario Bros | Reach the end of a generalized level | NP-hard | [24] |
| Minesweeper consistency | Is a given board consistent? | NP-complete | [25] |
| Generalized Sudoku | Solve an n² × n² Sudoku | NP-complete | [26] |
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
A brute-force solver that tries every ordering of 60 puzzle pieces would need more steps than there are atoms in the observable universe. Some growth rates are so vast they have no practical meaning. The number of atoms in the observable universe is roughly 1080; 2n crosses that threshold at n = 266, and n! crosses it at n = 59. The 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 onTSet, whose hash buckets store element indices and chain colliding elements through a per-element "next" index (Set.hin 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 itsParallelWritercannot grow the table while several jobs write to it at once. (Older Collections versions called itNativeMultiHashMap.) - Bevy ECS's archetype graph. Adding or removing a component changes an entity's archetype. Bevy caches, per archetype, an
Edgestable 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.cppandRadixSortShaders.usfin 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 + partand for immutable strings in Java and C#. Uses += parton astd::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
HashMapuses 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::vectorby 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(2depth), not O(depth). Naive recursive Fibonacci is the textbook case (about 1.6n 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) · logM/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
- 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.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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."
- 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."
- 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 Ω.
- 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.
- 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.
- 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.
- 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.
- 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.
- 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).
- 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.
- 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).
- 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.
- NVIDIA. "NVIDIA Turing GPU Architecture Whitepaper," 2018, "RT Core" section. PDF. Hardware-accelerated BVH traversal in fixed-function silicon.
- 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.
- Bevy Engine. "Use radix sort for sort phase and sprite sorting." GitHub issue #4291, 2022. github.com. Benchmarks of the
radsortcrate 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 shippedradsortfor its 3D phase sorts; later releases moved opaque meshes to unsorted bins and sort transparent phases with Rust's stable comparison sort, andradsortremains in sprite picking. - 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.
- 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.
- 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.
- Richard Kaye. "Minesweeper is NP-Complete." The Mathematical Intelligencer 22(2):9–15, 2000. NP-completeness proof for the Minesweeper Consistency Problem.
- 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.
- 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).
- Epic Games. "TMap Reference," Unreal Engine 5 documentation. dev.epicgames.com. Documentation of Unreal's hash-map data structure and its design choices.
- 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.
- 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."
- 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) logM/B(N/B)) transfer bound for sorting.
- 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.