All tutorials Mighty Professional
Build a Game Engine · Foundations

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.

Time~55 min LevelJunior to mid; review for senior PrereqsYou can read C++ or pseudocode at intermediate level. You've heard of arrays, hash tables, and trees. HardwareNone, but knowing that CPUs have caches helps in §6 and §13.
◂ Build a Game Engine Phase 0 · Foundations Next · Bit Shifting ▸
What you'll be able to do by the end

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:

Live · Pair-test cost as the scene scales
brute (O(n²))
···
sweep+prune
···
spatial hash
···
Each curve is the number of pair tests per frame as the scene grows, and the three boxes give the counts at the slider's scene size: at the default 800 objects, 319,600 for brute force, about 10,000 for sweep-and-prune and about 1,600 for the spatial hash. Raise the cell density to crowd more objects into each hash cell and watch the hash curve climb. Test counts stand in for time: each test is a handful of cycles, so the milliseconds depend on the hardware, but the ratios between the curves don't. Sweep-and-prune's average is O(n log n) with a worst case of O(n²) when every box overlaps every other[4]; the spatial hash is approximately O(n + k) where k is the number of actually-overlapping pairs, as long as the cell density stays bounded. The y axis is logarithmic: each gridline is ten times the one below it.

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
1877
Paul du Bois-Reymond compares growth rates symbolically.[6] His "infinitary calculus" writes f ≺ g when g grows faster than f, and ranks functions such as x2 and ex by their rate of increase. Hardy later adopted the ≺ symbol; Big O came from a different line.
1894
Paul Bachmann introduces the O symbol.[7] Volume II of his Analytische Zahlentheorie writes "f(x) = O(g(x))" with O standing for Ordnung ("order"). This is the first appearance of the notation that survived. Bachmann uses it for the error terms in his estimates of number-theoretic functions such as the number and sum of divisors.
1909
Edmund Landau adds little-o.[8] Landau's Handbuch der Lehre von der Verteilung der Primzahlen ("Handbook of the Theory of the Distribution of Prime Numbers") adopts Bachmann's big-O and introduces the lower-case o for strict asymptotic dominance. The pair is still called the Landau symbols in the math literature.
1914
Hardy and Littlewood extend the family.[9] G.H. Hardy and J.E. Littlewood introduce big-Ω as a number-theoretic lower bound (a non-vanishing remainder, "f is not little-o of g"). The symbol is borrowed later by computer science with a different and stricter definition.
1976
Knuth standardizes Big O, Big Ω, and Big Θ for algorithm analysis.[10] Donald Knuth's "Big Omicron and Big Omega and Big Theta" in SIGACT News formalizes the trio with the definitions algorithms researchers use today. Knuth wrote it because authors kept using O() for lower bounds (his example: rejecting a sorting method "because its running time is O(n²)") and he wanted a notation that kept the distinction visible. The modern Ω is stricter than Hardy and Littlewood's: it requires a uniform lower bound, not just an infinitely-often one.
1990
CLRS canonizes the asymptotic toolkit for teaching.[11] The first edition of Cormen, Leiserson, and Rivest (Stein joins for the second) puts asymptotic notation in an early "Growth of Functions" chapter of what becomes the most widely used algorithms textbook. Generations of undergraduates learn Big O from this presentation.
1997
Musser publishes introsort.[12] David Musser's "Introspective Sorting and Selection Algorithms" introduces the hybrid that runs quicksort but switches to heapsort when recursion depth exceeds 2 log₂ n. It turns the "worst case versus expected case" distinction into a library design decision: introsort guarantees O(n log n) worst case while keeping quicksort's speed on common inputs.
1999
Frigo, Leiserson, Prokop, Ramachandran formalize cache-obliviousness.[13] Counting block transfers between memory levels instead of CPU operations was already standard in the external-memory model of Aggarwal and Vitter (1988)[31]. Frigo et al. add the ideal-cache model and algorithms that hit the optimal transfer bounds without knowing the cache size, so one analysis covers every level of the hierarchy. Both models make the same point: Big O over memory transfers is sometimes the bound that matters, not Big O over arithmetic operations.
2010s
The "galactic algorithm" idea enters common usage.[14] A 2010 post on Lipton and Regan's blog names asymptotically superior algorithms whose constants are so vast they never beat the simpler approach on any realistically sized input (the name is Regan's). Coppersmith-Winograd matrix multiplication at O(n2.376) is a standard example; high-performance linear-algebra libraries implement the O(n³) product with cache blocking instead.

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]:

eq. 1 · big-O f(n) = O ( g(n) )   ⇔   ∃ c > 0, n₀ ≥ 0 : ∀ n ≥ n₀, 0 ≤ f(n) ≤ c · g(n)

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 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:

Live · Find c and n₀ that prove the bound
f(n)
3n² + 12n + 50
status
···
It opens on the worked example, c = 4 and n₀ = 16, where the status reads HOLDS. Drag n₀ down to 15 and it fails, because f(15) = 905 is more than 4 × 225 = 900. Raise c to 5 and n₀ can go as low as 9. Now switch g to n: no c on the slider works, and no c at all would, because the n² term eventually beats any multiple of n. Toggle to Ω or Θ to test the lower-bound and tight-bound definitions from §4. Θ needs two constants; the widget uses c for the upper curve and draws a second curve at c/2 as the lower one, so with g = n² and n₀ = 16 the sandwich (c/2)·g ≤ f ≤ c·g holds for any c from 4 to 6. The check is numerical: it samples n from n₀ up to about n₀ + 250.
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:

eq. 2 · concrete examples 3n² + 5n = O(n²), Θ(n²), Ω(n), o(n³), ω(n)

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.

A practical rule of thumb

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)ConstantHash table lookup (average), array index, push to a stack1 ns
O(log n)LogarithmicBinary search, balanced BST operation, typical BVH ray query20 ns
O(√n)Square-rootTrial-division primality test, sqrt decomposition1 µs
O(n)LinearLinear search, single pass over an array, building a histogram1 ms
O(n log n)LinearithmicComparison-based sort, FFT, sweep-and-prune broad phase20 ms
O(n²)QuadraticNested-loop pair test, bubble sort, naive matrix-vector product17 min
O(n³)CubicNaive matrix multiply, Floyd-Warshall all-pairs shortest paths32 years
O(2n)ExponentialBrute-force SAT over n variables, subset enumeration≫ age of universe
O(n!)FactorialBrute-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:

Live · Common growth rates on log-log axes
O(1) ··· O(log n) ··· O(n) ··· O(n log n) ··· O(n²) ··· O(n³) ··· O(2ⁿ) ···
Each line is one complexity class. The key under the chart gives each class's total time at the n marked by the vertical line: at the default 1,000 and 1 ns per step, O(n²) takes 1 ms and O(n³) a full second. Drag n up to a million to reproduce the table. The dashed line is how many steps fit in one 16.7 ms frame (60 fps), so where a curve crosses it is the largest n that class can handle per frame. Raise the per-operation time and the dashed line drops: slower steps mean smaller n fits. The n slider moves by a factor of about 1.26 per step, so every factor of ten gets the same travel. 1 ns per step is a middle-of-the-road figure: a modern core retires several simple instructions per cycle at 3 to 5 GHz, but a cache miss that goes to DRAM costs on the order of 100 ns.

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:

eq. 3 · crossover point 100n = n2 / 100 ⇒ n = 10,000

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.

Live · Where does the "worse" algorithm cross over?
crossover n
···
linear wins if
···
The two curves are the two algorithms' costs, plotted on ordinary (not log) axes, and the vertical line is where they cross. Drag either constant and the crossover moves to n = a × b: with the defaults, 100 × 100 = 10,000. Shrink a to 10 and the linear algorithm takes over from 1,000. The linear curve always wins eventually; whether it wins on the inputs you ship is the question.

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:

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.

Constants live forever

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:

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:

Live · Quicksort comparisons under three input patterns
comparisons at n
···
vs n log n
···
Pick an input pattern with the buttons and drag the array size; the boxes show the comparison count at that size and its ratio to n log₂ n. The "sorted" and "reverse" curves are the quadratic worst case, exactly n(n − 1)/2: 19,900 comparisons at the default 200 elements, 13× n log₂ n. Random input stays close to the n log n curve, about 1,500 comparisons at 200. The major C++ standard libraries avoid the quadratic case with Musser's introsort design[12]: they switch to heapsort once the recursion depth passes a limit (2 log₂ n in libstdc++ and libc++, about 1.5 log₂ n in MSVC), which guarantees O(n log n) in the worst case.

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).

Live · The cost of each push, with running average
peak push cost
···
amortized average
···
The top panel is the cost of each push, the bottom panel the running average. Drag the push count: the tall bars are the resizes, and each one makes the average jump before it decays again. At the default 128 pushes the biggest single push costs 65 and the average is 1.99. Now lower the growth factor to 1.5: resizes come more often, and the average rises to about 3.1. The growth factor trades resize cost against wasted memory. The C++ standard leaves it to the implementation: libstdc++ and libc++ double, which can leave up to half the buffer unused; MSVC's std::vector and Facebook's folly::fbvector grow by 1.5×, which wastes less but resizes more often. All of them have amortized O(1) push; the constant differs. The dashed line is the bound 1 + g/(g−1) for growth factor g.

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:

eq. 4 · the standard form T(n) = a · T(n / b ) + f(n)

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:

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 searchT(n) = T(n/2) + Θ(1)0Case 2 (c=0)Θ(log n)
Merge sortT(n) = 2T(n/2) + Θ(n)1Case 2Θ(n log n)
Karatsuba multiplicationT(n) = 3T(n/2) + Θ(n)log₂3 ≈ 1.585Case 1Θ(nlog₂3) ≈ Θ(n1.585)
Strassen matrix multiplyT(n) = 7T(n/2) + Θ(n²)log₂7 ≈ 2.807Case 1Θ(nlog₂7) ≈ Θ(n2.807)
Naive matrix multiply (recursive)T(n) = 8T(n/2) + Θ(n²)3Case 1Θ(n³)
BVH top-down (binned SAH, balanced splits)T(n) = 2T(n/2) + Θ(n)1Case 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 ratioDiagnosisSlope on log-log
~1O(1)0
~1 + 1/log nO(log n)tends to 0
~2O(n)1
~2.1–2.3O(n log n)slightly above 1
~4O(n²)2
~8O(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.

Live · Guess the complexity from measured data
slope (log-log fit)
···
doubling ratio
···
verdict
···
Each point is one simulated timing. Read the slope and doubling ratio, pick a class from the buttons to check your guess, then click "new mystery curve" for another. The slope is the least-squares fit of log T vs log n; the doubling ratio is computed from the two largest measured points (for the exponential case the sizes step by 1, so the ratio is per +1). Real profiling data is noisier than this. A slope fit separates n from n² easily but struggles to separate n from n log n over a narrow range of sizes.

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:

Live · Three broad-phase algorithms on the same scene
brute work/frame
···
SAP work/frame
···
hash work/frame
···
The circles drift and bounce; the faint grid is the spatial hash's cells. Each counter is one frame of broad-phase work. At the default 120 circles brute force does 7,140 tests while the other two stay around a thousand or below; drag the object count to 500 and brute force reaches 124,750. Then drag the cell size and watch only the hash counter move. Brute force counts every pair test. Sweep-and-prune counts the pairs whose x-intervals overlap during the sweep, plus an n log₂ n charge for sorting the endpoints. The spatial hash counts one insertion per cell an object touches plus the pair tests inside each cell. Small cells make each circle register in up to four cells, so insertions climb; large cells pack more circles into each cell and push the hash toward brute force inside the cell. In this scene the total bottoms out with cells two to three circle diameters wide, near the left end of the slider.

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.

Live · Brute force vs BVH, traced live
brute tests
···
BVH tests
···
speedup
···
Click "Fire ray" to shoot rays from the left edge; switch to BVH or both to see the boxes the tree tested. Raise rays per click to 32 for a steadier average, then drag the object count. Both methods look for each ray's closest hit. The BVH is built with a median split on the longer axis at each level, with up to four objects per leaf. Brute force has to test all n objects to be sure which hit is closest; the BVH tests the two child boxes of every node it enters, visits the nearer child first, and skips any box that starts beyond the best hit found so far. Going from 16 to 400 objects, the average BVH cost here rises from about 9 tests to about 19 while brute force rises 25-fold, so the speedup grows with n (from under 2× to about 20×). Rays that pass close to many boxes before their first hit cost the most. NVIDIA's RT cores (Turing and later) run this traversal and the ray-triangle tests in fixed-function hardware; that shrinks the constant, not the growth rate[19].

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:

Live · A* frontier under different heuristics
nodes expanded
···
path length
···
optimal?
···
Pick a search mode and click Run: the filled cells are the ones it explored, in order, and the line is the path it found. Compare the "nodes expanded" readout across the three modes on the same map, then try "New map" or more obstacles. The grid is 4-connected with unit step costs. Dijkstra is A* with h = 0; it expands every reachable cell closer than the goal, which on this grid is a diamond clipped by obstacles. The Manhattan heuristic is admissible here; A* explores a wedge biased toward the goal. Weighted A* multiplies h by 2.5 to push harder toward the goal; it usually expands fewer cells, but the path is no longer guaranteed optimal. The shape change is the improvement: Dijkstra's cost grows with the area it floods, while a heuristic that tracks the true distance closely keeps the expanded set near the path itself. The usual measure is the effective branching factor b*: the search expands roughly (b*)d nodes, and a better heuristic pushes b* toward 1.

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:

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.

draw_key.hpp · packing a sort key
#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):

YearAuthor(s)Exponent ωPractical?
1969Strassenlog₂7 ≈ 2.807Sometimes, for large matrices
1978Pan2.795No; constants too large
1981Schönhage2.522No
1990Coppersmith-Winograd2.376No; canonical galactic algorithm
2014Le Gall2.3728639No
2024Vassilevska Williams, Y. Xu, Z. Xu, Zhou[18]2.371552No
2025Alman, Duan, Vassilevska Williams, Y. Xu, Z. Xu, Zhou[18]2.371339No

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:

GameProblem statementComplexityReference
Generalized TetrisMaximize survival on a known sequence of piecesNP-complete[3]
SokobanPush boxes onto target tilesPSPACE-complete[23]
Super Mario BrosReach the end of a generalized levelNP-hard[24]
Minesweeper consistencyIs a given board consistent?NP-complete[25]
Generalized SudokuSolve an n² × n² SudokuNP-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.

Live · How big is big? Magnitude at small n
n!
···
2ⁿ
···
n³
···
Drag n and watch the n! and 2n bars race past the reference lines while the polynomials barely move. At the default n = 25, n! is already about 1025.2. All values are shown as their log10: a bar at 80 represents a number with 81 digits. The "atoms in universe" reference line (log₁₀ ≈ 80) and the "nanoseconds since big bang" line (log₁₀ ≈ 26.6) make the difference between "expensive" and "not finishable" visually concrete. n! crosses atoms-in-universe at n = 59 (59! ≈ 1.4 × 1080); 2n doesn't until n = 266 (2266 ≈ 1.2 × 1080), past the slider's range. Both set the limit of brute-force search.

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.

Live · Data structures versus operations
cost (this run)
···
asymptotic
···
Pick a structure and an operation, then click Run and see which cells it touched; change n and run again to see which costs grow. "Cost" is the number of structural visits (comparisons, pointer follows, hash probes) the operation performed. The asymptotic line shows the Big O for this (structure, operation) combo. Note that the playground's hash table assumes a good hash; degenerate hashes degrade to O(n) worst case.

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:

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:

20What's next

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

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) logM/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.

See also