Big-O, Intuitively

The 30-second version

Here is a small function you might write on your first week. It checks whether any email address appears twice in a list, by comparing every email with every email after it:

func hasDuplicate(emails []string) bool {
    for i := 0; i < len(emails); i++ {
        for j := i + 1; j < len(emails); j++ { // every later email
            if emails[i] == emails[j] {
                return true
            }
        }
    }
    return false
}

It passes every test. It's fast in staging, where there are 100 users. Then the product succeeds, there are 100,000 users, and the nightly job that calls it starts timing out. Here are real timings from this machine, next to a version that remembers the emails it has seen in a mapHash mapA key → value table (Go's map, JS's Map) that turns each key into a number with a hash function and uses it to jump straight to a slot. Lookups take about the same time however big it gets.:

Here is that fast version. It walks the list once, and for each email asks the map "have I seen you before?" — a check that takes about the same time however many emails the map holds:

func hasDuplicateFast(emails []string) bool {
    seen := make(map[string]bool, len(emails)) // emails seen so far
    for _, e := range emails {                 // one loop: n steps
        if seen[e] {                           // O(1) on average
            return true
        }
        seen[e] = true
    }
    return false
}

Nothing in the code changed — only the size of the input, which we call n. The nested-loop version does about n²/2 comparisons, so 1,000× more users means about 1,000,000× more work. That relationship between n and the amount of work is what Big-O notationBig-O notationA way to describe how an algorithm's cost grows as the input grows, ignoring constant factors: O(1) stays flat, O(n) grows in step with n, O(n²) quadruples when n doubles. writes down.

You don't need any maths beyond that to use Big-O well. You need to be able to look at code and say "this is the handshake shape", and know what to do about it.

What you'll learn

1. How to count steps instead of seconds, and why constants don't matter (§02), then the common growth shapes, with a race you can drag (§03).
2. How to read code for its Big-O, including the loops hidden inside library calls (§04), and what best/worst/average case mean (§05).
3. Amortized cost: why appending to a slice or array is O(1) even though it sometimes copies everything (§06), and space complexity (§07).
4. What a real stopwatch says (§08), how to fix accidental quadratic code (§09), and how complexity shows up in production systems — including attackers who exploit it (§10).

Counting steps, not seconds

Why not just time it?

Seconds depend on everything except the algorithm: the CPU, the language, what else the machine is doing, whether the data is already in a fast CacheCacheA small, fast store of answers you already computed or fetched, so the next request for the same thing skips the slow work. The hard part is knowing when a cached answer is out of date. close to the CPU. The same code can be 3× faster on your laptop than in CI. So instead we count steps: simple things that take roughly fixed time, like comparing two numbers, adding, or reading one item of an ArrayArrayItems stored one after another in a single block of memory, so item i is found by simple arithmetic in O(1). Go has fixed arrays and growable slices; JS arrays are growable..

The count of steps as n grows is called the algorithm's time complexityTime complexityHow the number of basic steps an algorithm takes grows as its input grows. Written with Big-O: O(n) means the steps grow in step with n. It describes the algorithm, so it's the same on every machine.. It's a property of the algorithm, so it's the same on every machine.

A worked count

Take hasDuplicate from §01 with n emails. The outer loop picks email 0 and the inner loop compares it with the n−1 emails after it; then email 1 with n−2 others; and so on, down to 0. Adding those up:

(n−1) + (n−2) + … + 1 + 0 = n(n−1)/2 = ½n² − ½n comparisons

With 100 emails that's 4,950 comparisons. With 100,000 emails it's 4,999,950,000 — about 5 billion. That one formula explains the 10 µs and the 11 seconds you saw. Here are those comparisons drawn as a grid — watch what doubling n does to it:

Only the biggest term survives

Real step counts are messy. Suppose careful counting gave some function 3n² + 10n + 50 steps: 3 steps per pair, 10 steps of bookkeeping per item, 50 steps of setup. Watch what each part contributes as n grows:

At small n the extras matter. At any n where performance is a question, the n² term is the whole story. Drag n yourself:

So Big-O makes two simplifications:

1. Drop the smaller terms. 10n and 50 vanish next to 3n² as n grows.
2. Drop the constant multiplier. 3n² and ½n² are both just O(n²). The constant depends on the machine and the language; the shape doesn't. Whatever the constant, doubling n makes n² four times bigger.

That's why hasDuplicate, at ½n² − ½n comparisons, is simply O(n²).

The common shapes of growth

Two more you'll meet occasionally: O(n³) (three nested loops over n, like comparing every triple of items: 8× when n doubles) and O(n!) (trying every ordering of n items — 10 items already have 3.6 million orderings).

The one that needs explaining: log n

log₂ nLogarithm (log₂ n)How many times you can halve n before reaching 1. log₂ 8 = 3, log₂ 1,000 ≈ 10, log₂ 1,000,000 ≈ 20. It grows very slowly: a thousand times more data adds only about 10. answers one question: how many times can you halve n before you get down to 1?

So an algorithm that throws away half of the remaining data at every step needs only about log₂ n steps. A thousand times more data costs just ten more steps. The classic example is Binary searchBinary searchFinding a value in a sorted list by checking the middle, then throwing away the half it can't be in, again and again. 1,000,000 items need only about 20 checks. over a sorted list:

And O(n log n) is "n items, each touched about log n times". It's what good sorting algorithms cost; §04 shows exactly where it comes from.

The race

Now put them side by side. Drag n from 1 to a billion. The time labels pretend that one step takes one microsecond (µs, a millionth of a second) — slow for a modern CPU, but it makes the numbers easy to feel:

Things to notice while you drag:

• For tiny n, nothing matters. At n = 10, every class finishes in about a millisecond or less.
• O(2ⁿ) dies first and hardest. At n = 64 it needs more steps than there are grains of sand on Earth (by common estimates). Exponential algorithms are only usable when n stays tiny (a few dozen at most).
• O(n²) is the one that bites in real code. It's fine at 1,000 and painful at 100,000 — the size that real tables, logs and user lists actually reach. Most "it was fine in testing" performance bugs are an accidental O(n²).
• O(log n) barely moves. A billion items, 30 steps. That's why databases and search structures work so hard to be logarithmic (see Indexes & B-Trees).

Reading code for its Big-O

Five rules that cover most code

1. A simple statement is O(1). Assigning, comparing, adding, reading xs[i] or m[key].
2. A loop over n items is n × (the cost of its body). A body of O(1) gives O(n).
3. Code in sequence adds; then keep the biggest. A loop over n followed by another loop over n is 2n = O(n). An O(n) loop followed by an O(n²) one is O(n²).
4. Nested loops multiply. A loop over n inside a loop over n is O(n²) — but only if both depend on n. If the inner loop always runs 3 times, it's 3n = O(n).
5. A loop that halves (or doubles) its counter is O(log n). It reaches the end after about log₂ n rounds (§03).

Some inputs have two sizes. Checking each of n orders against m products is O(n × m); reading two files one after the other is O(n + m). Keep both letters when the sizes are independent — don't quietly call it n².

Recursion: draw the tree

When a function calls itself (RecursionRecursionA function that solves a problem by calling itself on smaller pieces of it — e.g. a folder's size is the sum of its children's sizes, and a child folder computes its size the same way. It stops at pieces with no children.), loops are no help. Instead, draw the tree of calls, work out how much work each level of the tree does, and multiply by the number of levels.

Merge sortMerge sortA sorting algorithm: split the list in half, sort each half the same way, then merge the two sorted halves by repeatedly taking the smaller front item. Always O(n log n), but it needs O(n) extra memory. is the classic example. It splits the list in half, sorts each half by calling itself, and then merges the two sorted halves:

// import "cmp"

// mergeSort returns the items of xs in order (xs itself is left alone).
func mergeSort[T cmp.Ordered](xs []T) []T {
    if len(xs) <= 1 {
        return xs // 0 or 1 items: already sorted
    }
    mid := len(xs) / 2
    left := mergeSort(xs[:mid]) // sort each half the same way…
    right := mergeSort(xs[mid:])
    return merge(left, right)   // …then merge: O(n) on each level
}

func merge[T cmp.Ordered](a, b []T) []T {
    out := make([]T, 0, len(a)+len(b))
    for len(a) > 0 && len(b) > 0 {
        if a[0] <= b[0] { // take the smaller front item
            out, a = append(out, a[0]), a[1:]
        } else {
            out, b = append(out, b[0]), b[1:]
        }
    }
    out = append(out, a...) // one side may have leftovers
    return append(out, b...)
}

Step through it on 8 numbers and count:

Every level of the tree touches all n items once while merging, and there are log₂ n levels, so the total is n × log₂ n. That's the "n log n" of good sorts. (Go's slices.Sort and JavaScript's Array.prototype.sort use different, more refined algorithms, but they're O(n log n) too.)

Hidden loops: the bugs you can't see

A single line can contain a whole loop. Every method below scans its input from the start, so calling it once per item of a loop turns O(n) into O(n²):

On their own, each is fine. The bug is putting one inside a loop over the same data. That's the shape to train your eye for:

// Looks like one loop. It's two.
const allowed = users.filter((u) => !bannedIds.includes(u.id)); // ← includes scans bannedIds every time

Measured on Node 22 with 100,000 ids in each list, this pattern took about 12 seconds; the fixed version (§09) took about 30 ms.

Your turn: what's the Big-O?

Answer before you click. Each explanation says which rule applies.

function stars(rows) {
  for (let i = 0; i < rows.length; i++) {   // n times
    for (let j = 0; j < 3; j++) {           // always 3 times
      console.log(rows[i], "*");
    }
  }
}

func countDoublings(n int) int {
    steps := 0
    for i := 1; i < n; i *= 2 { // i = 1, 2, 4, 8, 16, …
        steps++
    }
    return steps
}

// users and bannedIds both have about n items
const allowed = users.filter((u) => !bannedIds.includes(u.id));

func minMax(xs []int) (int, int) {
    lo := xs[0]
    for _, x := range xs { lo = min(lo, x) } // n steps
    hi := xs[0]
    for _, x := range xs { hi = max(hi, x) } // n more steps
    return lo, hi
}

const queue = Array.from({ length: n }, (_, i) => i);
while (queue.length > 0) {
  const job = queue.shift(); // take the first item
  handle(job);               // assume handle is O(1)
}

function fib(n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2); // two calls, each almost as big as n
}

for i := 0; i < n; i++ {
    for j := i + 1; j < n; j++ { // starts after i: fewer steps each round
        compare(xs[i], xs[j])
    }
}

Best, worst and average case (and O vs Θ vs Ω)

The simple example: searching a list

Looking for a value by checking items from the start:

• Best case: O(1). It's the first item.
• Worst case: O(n). It's the last item, or not there at all.
• Average case: O(n). If it's equally likely to be anywhere, you check about n/2 items — still linear.

The best case is rarely useful ("my search is O(1) if you're lucky"). The worst case is the usual default because it's a promise: it can't get slower than this. The average case matters when the worst case is rare — which is the story of the next two examples.

Quicksort: a great average with a nasty worst case

QuicksortQuicksortA sorting algorithm: pick one item (the pivot), move smaller items before it and bigger ones after it, then sort each side the same way. O(n log n) on average, but O(n²) if the pivots keep landing at the edges. picks one item, the pivotPivotIn quicksort, the item the others are compared against to split them into “smaller” and “bigger”. A pivot near the middle splits the work in half; one at the edge barely splits it at all., moves smaller items to its left and bigger ones to its right, then sorts each side the same way. Here's the textbook version that always uses the first item as the pivot:

func quicksort[T cmp.Ordered](a []T) {
    if len(a) < 2 {
        return
    }
    pivot, p := a[0], 0 // ← first item as the pivot: the weak spot
    for i := 1; i < len(a); i++ {
        if a[i] < pivot { // move smaller items to the front
            p++
            a[p], a[i] = a[i], a[p]
        }
    }
    a[0], a[p] = a[p], a[0] // put the pivot between the two groups
    quicksort(a[:p])        // everything smaller than the pivot
    quicksort(a[p+1:])      // everything bigger
}

On random input, the pivot lands somewhere near the middle, so each split roughly halves the data: log n levels of n work, O(n log n), the same tree as merge sort.

On input that's already sorted, the first item is the smallest. Nothing is smaller than it, so the "smaller" side is empty and the "bigger" side has n−1 items. Every level peels off just one item: n levels of up to n work, O(n²). Measured on this machine:

Sorted input isn't exotic. It's what you get when you re-sort a list that barely changed, or sort rows that came out of a database indexIndex (database)An extra, sorted data structure the database keeps next to a table so it can find rows by a column without reading the whole table — like the index at the back of a book. (which already returns them in order). That's why real libraries never use a naive pivot: Go uses pdqsortpdqsortPattern-defeating quicksort, the algorithm behind Go's sort and slices.Sort since Go 1.19. A quicksort that picks pivots carefully, spots already-sorted runs, and falls back to heapsort if splits go badly, so it's O(n log n) even in the worst case., and V8 uses TimSortTimSortA sorting algorithm that finds runs that are already in order and merges them, like a smart merge sort. V8 uses it for Array.prototype.sort. O(n log n) worst case, and close to O(n) on nearly sorted data. for Array.prototype.sort. Both guarantee O(n log n) in the worst case.

Hash maps: O(1) on average

A Hash mapHash mapA key → value table (Go's map, JS's Map) that turns each key into a number with a hash function and uses it to jump straight to a slot. Lookups take about the same time however big it gets. lookup is O(1) on average: a Hash functionHash functionA function that turns any input (a string, a file) into a fixed-size number or fingerprint. The same input always gives the same output, and small changes give very different outputs — used to spread keys across buckets or servers, and (with cryptographic hashes like SHA-256) to detect tampering. turns the key into a slot number and you jump straight there. In the worst case, if many keys land on the same slot, the map has to check them one by one, and a lookup becomes O(n). Real maps keep this rare with good hash functions and by growing as they fill up; Hash Maps shows how. When people say "maps are O(1)", they mean the average.

O, Ω and Θ in plain words

You'll see three symbols. All three describe how a cost grows — they just put the bound in different places:

A ceiling can be loose. Linear search is technically also O(n²) — "at most n²" is true, just useless. Θ removes that slack. In everyday engineering talk, people say "O" but mean the tight Θ bound, and this page does the same.

Amortized cost: why append is O(1)

The problem: arrays can't stretch

An ArrayArrayItems stored one after another in a single block of memory, so item i is found by simple arithmetic in O(1). Go has fixed arrays and growable slices; JS arrays are growable. is one block of memory with a fixed size. A Go SliceSlice (Go)Go's growable list type, written []T: []byte is a list of bytes, []Node a list of Nodes. Like a JS array, but every item has the same type. or a JavaScript array feels growable, but underneath it's a fixed-size array with some spare room. The number of slots is its capacityCapacityHow many items fit in the array behind a growable list before it has to grow. In Go, cap(s); the length len(s) is how many are actually used. JS arrays have a hidden capacity too.; the number in use is its length.

While there's spare room, an append just writes into the next free slot: O(1). When the array is full, the runtime has to allocate a bigger array and copy every existing item into it before writing the new one. That single append is O(n). (The memory side of this — the allocations it causes — is covered in Stack vs Heap §09.)

So is append O(1) or O(n)? Both, for different appends. The question that matters for a loop is: what does a long run of appends cost in total?

The doubling trick

Suppose the array doubles its capacity whenever it fills up. Walk through 16 appends starting from empty: it grows at appends 1, 2, 3, 5, 9 (to capacities 1, 2, 4, 8, 16), copying 0 + 1 + 2 + 4 + 8 = 15 items in total. Add the 16 writes and the whole run costs 31 steps: under 2 per append.

That isn't luck. Each copy is half the size of the next one, so all the copies so far add up to less than the current size: 1 + 2 + 4 + … + n/2 < n. n appends cost less than n writes plus n copies — under 2n steps, so O(1) each, on average. Try it, then flip the toggle to a policy that grows by a fixed +4 slots instead:

The rule to remember: grow by a ratio (×2, ×1.5, ×1.25), never by a fixed amount. Any ratio above 1 gives O(1) amortized; a smaller ratio just means more frequent, smaller copies. With growth factor g, each item gets copied on average about 1/(g−1) times: once for ×2, four times for ×1.25.

What Go and V8 actually do

Here's Go's real growth for a slice of ints, on Go 1.24:

var s []int
for i := 0; i < 2000; i++ {
    before := cap(s)
    s = append(s, i)
    if cap(s) != before { // append had to grow the array
        fmt.Printf("append #%d: cap %d → %d, copied %d\n", i+1, before, cap(s), len(s)-1)
    }
}

append #1: cap 0 → 1, copied 0
append #2: cap 1 → 2, copied 1
append #3: cap 2 → 4, copied 2
append #5: cap 4 → 8, copied 4
…
append #257: cap 256 → 512, copied 256
append #513: cap 512 → 848, copied 512
append #849: cap 848 → 1280, copied 848
append #1281: cap 1280 → 1792, copied 1280
append #1793: cap 1792 → 2560, copied 1792

Go doubles while the capacity is below 256. Past that, each growth adds (cap + 768) / 4, so the factor shrinks gradually from ×2 towards ×1.25 as the slice gets bigger — you can see ×1.66, ×1.5, ×1.4 above, and by 100,000 items it's about ×1.25. Then the size is rounded up to one its memory allocator likes (512 + 320 = 832 became 848). That's nextslicecap in Go 1.24's runtime/slice.go. These details can change between versions — but it's always a ratio. Counting copies for 1,000,000 appends, we got 4,154,015: about 4.2 copies per append — close to the 1/(1.25−1) = 4 that the "about 1/(g−1)" rule predicts for a slice that has mostly grown at ×1.25. A constant.

V8, the JavaScript engine in Chrome and Node, grows an array's backing store to about 1.5× the new length, plus 16 (checked on Node 22 by inspecting the array's internals; also an engine detail). So push is O(1) amortized too.

Amortized is not the same as average

• Amortized is a guarantee. It holds for every sequence of operations, with no luck involved. Any n appends cost O(n) total.
• Average case (§05) is about typical inputs. A hash map is O(1) on average, but a bad set of keys can make it slower.

And amortized O(1) still means one append in a while is slow. In a batch job nobody notices. In code that must answer within microseconds every time, the occasional big copy shows up as a latency spike. When you know the final size, skip the copies entirely:

out := make([]Item, 0, len(rows)) // length 0, capacity len(rows): never grows
for _, r := range rows {
    out = append(out, toItem(r))
}

The same idea appears all over: Go's strings.Builder grows its buffer by a ratio, hash maps double their table when they get too full (Hash Maps), and a queue built on a slice (§09) moves items only occasionally. Each one is "usually O(1), sometimes O(n), O(1) amortized".

Space complexity: memory counts too

Space complexitySpace complexityHow much extra memory an algorithm needs as its input grows — new lists, maps, copies, and the call stack under recursion. Usually you don't count the input itself. usually counts only the extra memory an algorithm uses on top of its input — sometimes called auxiliary space. Reading a list you were given costs nothing extra; building a second list of the same size costs O(n).

Three places extra memory comes from

1. Copies and new collections. Building a result of n items is O(n) space. So is a lookup table: the map in §01's fast hasDuplicate holds up to n emails. That's the trade it made — O(n) extra memory to go from O(n²) to O(n) time. Usually a great deal; occasionally (huge n, tight memory) not.

2. In place vs copying. An algorithm that rearranges the input inside its own memory is called in placeIn placeWorking inside the input's own memory instead of building a copy, so only O(1) extra space is needed. slices.Reverse and JS's arr.reverse() are in place; arr.toReversed() returns a copy. and needs only O(1) extra space:

// O(n) extra space: a whole second slice.
func reversedCopy(xs []int) []int {
    out := make([]int, len(xs))
    for i, x := range xs {
        out[len(xs)-1-i] = x
    }
    return out
}

// O(1) extra space: swap the ends, walk inwards.
func reverseInPlace(xs []int) {
    for i, j := 0, len(xs)-1; i < j; i, j = i+1, j-1 {
        xs[i], xs[j] = xs[j], xs[i]
    }
}
// The standard library has the in-place one: slices.Reverse(xs)

Both are O(n) time. They differ in memory — and in behaviour: the in-place version changes data the caller might still be using. In JS, sort() and reverse() work in place, while the newer toSorted() and toReversed() return copies.

3. The call stack. Every function call that hasn't returned yet keeps a Stack frameStack frameOne function call's entry on the call stack (one “plate”), holding that call's local variables. on the Call stackCall stackThe list of functions that are running right now — each one sits on top of the one that called it. When a function returns, its entry (and its local variables) is thrown away. (see Stack vs Heap). So recursion uses memory proportional to how deep it goes, even if it never builds a single collection.

Recursion depth: the hidden O(n)

Merge sort's tree (§04) is only log₂ n levels deep, so it never has more than about log n calls waiting at once. Quicksort's depth depends on its pivots (§05):

That's not a theoretical worry. Our textbook JavaScript quicksort from §05, given 10,000 already-sorted numbers, crashed before it could get slow:

RangeError: Maximum call stack size exceeded

On Node 22 with default settings, a simple recursive function gets roughly 10,000 calls deep before hitting that error (we saw about 9,600 on this machine; the exact limit varies with the Node version, the settings and how big each frame is). Go grows goroutine stacks on demand up to a 1 GB maximum, so the same Go quicksort didn't crash on 100,000 sorted items — it just took 2 seconds and used O(n) stack. Real quicksorts recurse into the smaller side first and loop over the bigger one, which caps the depth at O(log n) whatever the input.

Theory meets the stopwatch

Benchmarking across n

A single timing tells you little about growth. Time the same code at several sizes, each double the last. In Go, a BenchmarkBenchmarkA small program that runs one piece of code many times and measures how long it takes (and, in Go with -benchmem, how many bytes and allocations it makes per run). with one sub-benchmark per size does exactly that:

// imports: fmt, math/rand/v2, slices, testing
var sink bool // results go here so the compiler can't skip the work

func BenchmarkContains(b *testing.B) {
    for _, n := range []int{1_000, 2_000, 4_000, 8_000} {
        s := make([]int, n)
        for i := range s {
            s[i] = rand.IntN(1 << 40)
        }
        b.Run(fmt.Sprint(n), func(b *testing.B) { // one sub-benchmark per size
            for b.Loop() { // runs the body as many times as needed to time it
                sink = slices.Contains(s, -1) // -1 is never there: the worst case
            }
        })
    }
}

$ go test -bench .
BenchmarkContains/1000-4     4101075     278.6 ns/op
BenchmarkContains/2000-4     2142190     548.7 ns/op
BenchmarkContains/4000-4     1000000      1064 ns/op
BenchmarkContains/8000-4      565812      2123 ns/op

Read it as a doubling test: n doubles each line, and the time goes 279 → 549 → 1,064 → 2,123 ns. ×2 each time: linear, O(n). If it went ×4 you'd have O(n²); ×1 (flat) would be O(1); "+ a few ns" would be O(log n).

Five classes, measured

We ran the same kind of benchmark for five operations, from a thousand to a million items. On log-log axes (both axes on a log scaleLog scaleA chart axis where each equal step means multiplying (×10 or ×2) instead of adding, so tiny and huge values fit on one chart. A straight line on log-log axes means a power of n: the steeper, the bigger the power.), each class becomes a straight line whose steepness is the power of n: flat for O(1), slope 1 for O(n), slope 2 for O(n²).

Flip to Time ÷ formula. This is how you fit the curve: divide each measurement by the formula you suspect (n, n log₂ n, n²…) and see whether the result stays flat. For the sort and the all-pairs loop it stays almost perfectly flat — the formula explains the growth completely. For the map and binary search it doesn't, and that's the interesting part.

When Big-O and the stopwatch disagree

"O(1)" isn't one fixed time. The map lookup went from about 5 ns at a thousand keys to about 40 ns at a million: same number of steps, but at a million keys the map no longer fits in the CPU's fast caches, so most steps wait for main memory. Big-O counts steps; it doesn't know that some steps cost 1 ns and others 100 ns. CPU Caches explains why, and how much.

For small n, constants win. Here's an O(n) linear scan of a []int against an O(log n) lookup in a binary search tree (one separately allocated node per key; see Trees & Tries), measured on this machine:

Up to about a hundred keys, the "worse" algorithm ties: scanning a few cache lines in order is extremely fast, while each tree step follows a PointerPointer (*T, &v)A value that holds the memory address of another value instead of a copy of it. In Go, &v takes v's address and *T is the type “pointer to T”; changes made through a pointer are seen by everyone holding it. JS objects behave like this automatically. to somewhere else in memory. Only as n grows does the better shape take over — and then it wins by more every time n doubles. (CPU Caches §10 has the same experiment against a map.)

Measuring in JavaScript

There's no built-in benchmark runner, but the same doubling test works with performance.now(). Do a warm-up run first, because the engine compiles hot functions to faster machine code only after they've run a while (JIT compilerJIT compiler (TurboFan)A just-in-time compiler turns code into machine code while the program runs. V8 starts by interpreting your JS, and recompiles “hot” functions with its optimizing compiler, TurboFan, using what it has learned about them.):

for (const n of [1_000, 2_000, 4_000, 8_000]) {
  const xs = Array.from({ length: n }, (_, i) => i);
  work(xs); // warm-up: let the JIT optimize it
  const t = performance.now();
  for (let r = 0; r < 100; r++) work(xs);
  console.log(n, ((performance.now() - t) / 100).toFixed(3), "ms");
}

Whatever the language, measure at realistic sizes and several of them, run each more than once, and be suspicious of one-off numbers: this machine was shared with other work, and individual runs varied by up to 2×. For Go, Stack vs Heap §08 covers -benchmem, -count and comparing runs properly.

Fixing accidental quadratic code

1. Looking things up in a list, inside a loop

The most common one by far. For each item, search another list:

// Keep the users who are NOT banned (users: []User, banned: []int).

// O(n × m): slices.Contains scans banned for every user.
var allowed []User
for _, u := range users {
    if !slices.Contains(banned, u.ID) { // ← hidden loop
        allowed = append(allowed, u)
    }
}

// O(n + m): build a set once, then each check is O(1) on average.
set := make(map[int]struct{}, len(banned))
for _, id := range banned {
    set[id] = struct{}{}
}
var allowedFast []User
for _, u := range users {
    if _, ok := set[u.ID]; !ok {
        allowedFast = append(allowedFast, u)
    }
}

When you need to keep more than presence — group orders by customer, count words — the same idea applies with a map from key to value. If both lists are already sorted, walking them side by side with two indices is also O(n + m), with no extra memory.

2. Building a string with += in Go

Go strings can't be changed in place. So s += "line\n" allocates a new string and copies all of s into it, every time: the k-th step copies about k lines, which adds up to O(n²) bytes copied.

// O(n²): each += copies everything built so far.
s := ""
for i := 0; i < n; i++ {
    s += "line\n"
}

// O(n): strings.Builder appends into a growing buffer (amortized, §06).
var b strings.Builder
for i := 0; i < n; i++ {
    b.WriteString("line\n")
}
s := b.String()

Measured with n = 100,000: Go's += took ~8.8 seconds; strings.Builder took ~0.7 ms. In Node 22, += with a million pieces took ~190 ms and join ~90 ms, because V8 represents concatenations as a ropeRope (string)A string stored as a tree of pieces instead of one block of characters. Concatenating just adds a node, so a + b is cheap; the pieces are joined into one block later, when needed. V8 uses this for JS string +. instead of copying each time. That's an engine optimization, not a language guarantee — so in JS it's fine to use +=, but join is the safe habit for big outputs.

3. Using a JS array as a queue with shift()

arr.shift() removes the first item, and every other item has to move down one slot: O(n). Draining a big array with it is O(n²). Measured on Node 22: 100,000 shifts took ~0.7–1.2 s; reading the same items by moving an index took ~5 ms.

The fix: keep a head index, and only once in a while throw away the used-up front part:

// Queue is a FIFO queue on a slice. Pop moves a head index
// instead of shifting every item.
type Queue[T any] struct {
    items []T
    head  int // index of the next item to pop
}

func (q *Queue[T]) Push(v T) { q.items = append(q.items, v) }

func (q *Queue[T]) Pop() (T, bool) {
    var zero T
    if q.head == len(q.items) {
        return zero, false // empty
    }
    v := q.items[q.head]
    q.items[q.head] = zero // drop the reference so the GC can free it
    q.head++
    if q.head > 1024 && q.head*2 > len(q.items) { // mostly dead space: compact
        n := copy(q.items, q.items[q.head:])
        clear(q.items[n:])
        q.items = q.items[:n]
        q.head = 0
    }
    return v, true
}

Compaction copies only when at least half the slice is dead space, so each item is copied at most a few times over its life: O(1) amortized per operation, the same argument as §06. For a fixed-size queue, a Ring bufferRing bufferA fixed-size array used as a queue: the read and write positions wrap around to the start when they reach the end, so nothing ever has to be shifted. avoids even that.

4. Copying inside a loop

Anything that builds a fresh copy is O(n), so doing it once per item is O(n²):

let result = [];
for (const row of rows) {
  result = [...result, transform(row)]; // ← copies all of result, every time
}
// fix: result.push(transform(row)) — or just rows.map(transform)

Measured on Node 22: 10,000 rows took ~110 ms with the spread and ~0.2 ms with push.

At 50,000 rows the spread version took about 10 seconds — roughly 100× the time for 5× the rows, when O(n²) predicts 25×. The number of item copies did grow exactly 25×; what changed is the cost of each copy, which we measured directly (total time ÷ items copied):

The jump starts around 15,000 items. Around there an array's items take about 128 KB, and V8 stops storing it in its normal memory area for new objects and puts it in a separate "large object" area instead (we checked with Node's v8.getHeapSpaceStatistics(): 10,000-item arrays went to the normal area, 16,500-item ones to the large-object area). Creating each new array there is slower, and it's likely the same reason the shift() shortcut above stopped working at that size. Garbage collection — cleaning up all the discarded copies — also grew, from about 30 ms at 10,000 rows to about 1.6 s at 50,000 (measured with node --trace-gc). Lesson: Big-O gives the shape; the real cost per step can get worse as the data gets bigger, never better. The same trap in Go is slices.Insert(s, 0, x) in a loop (inserting at the front shifts everything) or append([]T{x}, s...).

5. Re-sorting or re-scanning on every step

for _, score := range incoming {
    scores = append(scores, score)
    slices.Sort(scores)                  // ← O(n log n) per item → O(n² log n) total
    fmt.Println("top:", scores[len(scores)-1])
}

If you only need the top, track the maximum as you go: O(1) per step. If you need the top k, or the smallest item over and over, a Priority queuePriority queueA queue that hands out the most important item first instead of the oldest. Usually built on a heap, so adding and removing are fast even with many items. (a heap) does each step in O(log n) — see Heaps & Priority Queues. If you need the sorted list only at the end, sort once, after the loop.

6. The database version: N+1 queries

The same shape with a network in the middle: load a list of n posts, then run one more query per post to fetch its author. Each query is a full round trip to the database and back (see Round-trip timeRound-trip time (RTT)How long it takes for a message to go from one machine to another and for the reply to come back. Roughly 1 ms inside a data center, 70–150 ms across an ocean.), so the page does n + 1 round trips instead of 2. It's O(n) round trips — and one round trip (about 0.5 ms inside a data center) costs as much as hundreds of thousands of in-memory steps. N+1 Queries & ORMs covers how to spot it and the four standard fixes (a JOIN, a batched IN query, eager loading, DataLoader).

Staff-level: complexity in real systems

A request's cost is the sum of its parts

Take an endpoint that returns one customer's orders. Its cost is roughly:

Add them and keep the biggest term (§02). With the index, the request is O(log N + k): it costs about the same whether the table holds a thousand orders or a billion. Without it, it's O(N): every customer's request gets slower as the whole business grows, even customers with two orders. (Indexes & B-Trees shows how the index gets that log N.)

That's the staff-level habit: a request's cost should scale with what the request asks for, not with the size of the system. When it scales with the system, it's a time bomb — the timer is your growth rate.

Tail latency lives at the big-n users

If cost is O(k) in a customer's data, most requests are cheap and a few are huge: the customer with 50,000 orders, the user following 2 million accounts. They don't move the average, but they set your p99p99 (99th percentile)The value that 99% of measurements are below — i.e. how bad the slowest 1% is. Averages hide slow outliers; p99 shows them. and your Tail latencyTail latencyThe latency of the slowest few requests — usually reported as p99 or p99.9. It's what your unluckiest users feel, and it grows much faster than the average under load., and they're often your most important customers.

So for every per-request loop, ask: what's the largest k anyone has, and what's the largest they could have? Then bound it: paginate, cap batch sizes, refuse inputs over a limit. A limit turns "O(n) with n unbounded" into "O(n) with n ≤ 1,000", which is effectively constant. The same thinking applies to amortized operations (§06): the average is O(1), but the one slow resize lands on somebody's request.

When the attacker chooses your worst case

§05 showed that an algorithm can be fast on typical input and slow on bad input. If outsiders control the input, assume they'll find the bad input. These are called algorithmic complexity attacksAlgorithmic complexity attackA denial-of-service attack that sends input chosen to hit an algorithm's worst case — colliding hash keys, a regex's slow path — so a tiny request makes the server do enormous work.: a small request that makes your server do enormous work — a cheap denial of serviceDenial of service (DoS)Making a service unusable for its real users — for example by sending requests that tie it up with so much work it can't answer anyone else. Unlike a DDoS, one attacker with one machine can be enough..

Hash flooding. A hash map is O(1) on average and O(n) when keys collide (§05). In 2011, researchers showed that many web frameworks' maps could be flooded: send a form with a few thousand field names chosen to land in the same slot, and inserting them costs O(n²). The defense is a random seed mixed into the hash function, so attackers can't predict which keys collide. Go picks a random seed for every map, and V8 randomizes its string hashes per process. Your remaining job: cap how many keys a request can create (form fields, JSON object keys, query parameters). Hash Maps covers collisions in depth.

ReDoS (regular-expression denial of service). Most regex engines, including JavaScript's, use backtrackingBacktrackingTrying a choice, and if it leads to a dead end, going back and trying the next one. JavaScript's regex engine matches this way, which is why some patterns can take exponential time on inputs that almost match.: on a failed match they go back and try another way to split the input. A pattern with a quantifier inside a quantifier, like (a+)+, can split n characters in about 2ⁿ ways — and on input that almost matches, it tries them all:

const re = /^(a+)+$/; // nested quantifiers: the classic ReDoS shape
for (const n of [20, 22, 24, 26, 28]) {
  const input = "a".repeat(n) + "!"; // almost matches, then fails at the end
  const t = performance.now();
  re.test(input);
  console.log(n, (performance.now() - t).toFixed(1), "ms");
}

At 40 characters the JavaScript version would run for over an hour, blocking Node's single thread the entire time. Real incidents have come from regexes for email validation, user agents and log parsing. Defenses: avoid nested quantifiers and overlapping alternatives ((a|a)*); limit input length before matching; and when users supply the pattern or the input is hostile, use a linear-time engine (Go's regexp, or a binding to RE2 in Node).

Choose data structures by the operations you need

Big-O's most practical use is picking the right structure up front. List the operations your code does most often, then pick the structure that makes those cheap:

Often you need two operations that no single structure does well — "look up by id" and "list in order". Then keep two structures in sync (a map plus a sorted slice, or a map plus a heap), paying a bit of memory for both operations being fast. An LRU cache is the classic case: a map for lookups plus a linked list that keeps the usage order.

Pitfalls gallery

Check yourself

Predict the answer before you click. Q1 is covered in §02, Q2 in §09, Q3 in §03, Q4 in §08, Q5 in §06 and Q6 in §10.

let result = [];
for (const row of rows) {
  result = [...result, transform(row)];
}

Cheat sheet

Everyday operations

Reading code in 10 seconds