Big-O & Asymptotic Analysis

The 10-second versionCopy Anchor Link

Big-O is a language for describing how work grows. It doesn't tell you how many milliseconds something takes on your laptop. It tells you: as the input gets bigger and bigger, does the cost stay flat, grow in a straight line, blow up quadratically, or explode exponentially? That single question is what separates an algorithm that scales to a billion users from one that dies at ten thousand.

Why this existedCopy Anchor Link

Here's the problem that kicked all of this off. In the late 1800s, mathematicians were studying prime numbers and series — things like "how many primes are there below n?" — and they kept needing to say something vague but precise: "this quantity grows roughly like that one."

They didn't care about the exact constant. 1000n and 3n both "grow linearly." What mattered was the shape of the growth.

• 1894 — German mathematician Paul Bachmann introduces the O symbol in his book Die Analytische Zahlentheorie, using it to bound the size of error terms.
• 1909 — Edmund Landau adopts and spreads the notation, which is why it's sometimes still called Landau notation.
• 1970s — Donald Knuth takes this dusty number-theory tool and points it at computer programs. His 1976 paper "Big Omicron and Big Omega and Big Theta" argues that computer scientists should use the whole family (O, Ω, Θ) rigorously, not just wave the O symbol around.

Why did it matter? Because before a shared vocabulary, "this is fast" meant nothing. Two engineers could argue for hours with zero common ground. Big-O gave them a contract: ignore the machine, describe the growth, and we can compare honestly.

Inside the inventor's headCopy Anchor Link

Picture Bachmann staring at a messy error term like n log n + 7n + 42. He doesn't want to carry that whole expression around; it obscures the essence. His instinct is the same one you have when you squint at a graph: what dominates when n gets huge?

So he tries something. What if he collapses everything into one symbol and keeps only the ceiling — the worst-case shape? He lands on writing f(n) = O(g(n)), meaning "f never outruns some fixed multiple of g once n is large enough."

The first attempt at a rule — "keep the biggest term" — is almost right, and that's the fun part. Watch it break:

That's the subtle pivot that trips up almost everyone. Big-O is not about small inputs. You deliberately throw away the small-n behavior, the constants, and the lower-order noise, because hardware and compilers change those — but the growth shape is a property of the algorithm itself.

Knuth's later insight pushes it further: O only gives an upper bound. Something that grows linearly is also O(n²) (it just never uses the extra room). To say "grows exactly like," you need Θ. To say "at least as fast," Ω. One symbol became three, because one was too blunt for real arguments.

The final approachCopy Anchor Link

Here is the complete working idea. We define three bounds over a function f(n):

Formally, f(n) = O(g(n)) when there exist constants c > 0 and n₀ such that for every n ≥ n₀, f(n) ≤ c · g(n). In plain words: past some point, f stays under a scaled copy of g forever.

The rules you actually useCopy Anchor Link

The growth ladderCopy Anchor Link

Reading from "basically free" to "please don't do this":

It in codeCopy Anchor Link

The same idea, three dialects. Notice we're not measuring time — we're counting the growth of operations as n scales.

// O(1): one lookup, no matter how big the array isconst first = (a) => a[0];// O(n): touch every element exactly oncefunction sum(a) {  let total = 0;  for (const x of a) total += x;  return total;}// O(n^2): for every element, scan the whole array againfunction countDuplicates(a) {  let count = 0;  for (let i = 0; i < a.length; i++)    for (let j = 0; j < a.length; j++)      if (i !== j && a[i] === a[j]) count++;  return count;}

The third function is the trap. It looks like a nested loop because it's the same shape as the second one plus a level. That level is the difference between "fine for a million items" and "melts your machine at ten thousand."

A worked traceCopy Anchor Link

Count the operations for n = 4 in countDuplicates. The inner if runs n · n = 16 times regardless of data. Double n to 8 and it runs 64 times — four times more work for two times the input. That "factor of four" is the fingerprint of n², and you can feel it in a stopwatch before you can prove it on paper.

Where you meet it todayCopy Anchor Link

• Databases. An index is literally the difference between O(n) (scan every row) and O(log n) (walk the B-tree). This is why EXPLAIN output matters so much.
• Autocomplete. A trie lookup is O(length of prefix), not O(number of words) — that's why your editor can suggest while you type.
• Interviews & code review. "What's the complexity?" is the shorthand for "will this still work when the data is 100× bigger?"

// O(1) — a Set turns "have I seen this?" from a scan into a lookupconst seen = new Set();for (const id of ids) {  if (seen.has(id)) return true;  seen.add(id);}

RecapCopy Anchor Link

• Big-O describes growth, not absolute speed — constants and hardware are deliberately ignored.
• O is an upper bound, Ω a lower bound, Θ a tight bound. Knuth gave us all three because one wasn't enough.
• The mechanical recipe: drop constants → drop lower terms → add for sequence, multiply for nesting.
• The ladder to memorize: 1 < log n < n < n log n < n² < 2ⁿ < n!.

Next up: Recursion & the Call Stack — the other foundational tool you'll reach for constantly.