Complexity: Big-O, Amortized, and the Cost Model That Matters

In February 2021, an anonymous programmer who goes by t0st got tired of waiting. GTA Online, the online mode of one of the most profitable entertainment products ever made, took around six minutes to load on his machine. Not to download. To load, every single session, and it had been that way for seven years. Players had complained for so long it had become a meme.

t0st didn't have the source code. He attached a profiler to the running game and watched where the time went. Almost all of it landed in two places, and both of them are the subject of this lesson.

First: the game loads a roughly 10MB JSON file describing about 63,000 purchasable items, and it parsed that file with repeated calls to sscanf. Here's the trap. sscanf on many C runtimes calls strlen on the input first, every single call, to know where the string ends. So parsing token number one scanned all 10 megabytes. Parsing token number two scanned all 10 megabytes again. Sixty-three thousand tokens, each one re-walking a 10MB buffer. The work done was proportional not to the size of the file but to the size of the file times the number of tokens.

Second: after parsing each item, the game checked whether it had already seen that item's hash by scanning a plain array of everything seen so far, one entry at a time. Item 1 checks 0 entries. Item 60,000 checks 59,999 entries. Add it all up and that's about two billion comparisons to deduplicate a list that, as t0st pointed out, probably contained no duplicates at all.

His fix was embarrassingly small. Cache the string length so it's computed once instead of 63,000 times. Replace the array scan with a hash set, where checking "have I seen this?" takes the same tiny amount of work no matter how many items came before. Load time dropped by around 70 percent. Rockstar confirmed the diagnosis, shipped the fix, and paid him $10,000 through their bug bounty program.

Here's the part that matters for us. That code was not written by fools. When the item catalog was small, in 2013, the code was fine. Nobody could feel the difference between "scan the buffer once" and "scan it per token" at small n. The cost was growing with the catalog, quietly, every time Rockstar added a weapon or a car, and nobody on the team had priced the code in the right currency. This lesson is about that currency.

Counting steps, not seconds

The obvious way to measure code is with a stopwatch: run it, time it. The stopwatch is honest but it answers the wrong question. It tells you how fast this code ran on this machine, with this compiler, at this input size, while Slack was doing whatever Slack does in the background. Change any of those and the number changes. Worse, the stopwatch can't warn you about the future. GTA Online's loading code would have benchmarked beautifully in 2013.

So instead of seconds, we count steps, and we count them as a function of the input size, which we call n. The model is deliberately crude: assume every basic operation costs exactly 1. An addition costs 1. A comparison costs 1. Reading or writing one variable or one array slot costs 1. This is called the RAM model (random access machine), and its core assumption is that any single operation, including touching any location in memory, costs the same constant amount. Hold onto that assumption; we're going to break it at the end.

Let's count something. Here's a function in pseudocode, the notation this course uses on screen so the ideas stay language-agnostic:

function sum(items):
    total = 0                 # 1 step
    for each x in items:      # runs n times
        total = total + x     # 2 steps per iteration (add, store)
    return total              # 1 step

One step to initialize, one to return, and the loop body does a couple of steps for each of the n items. Total: something like 2n + 2 steps. The exact count depends on how you tally (does the loop's own bookkeeping count? one step or two per assignment?), and that's the first lesson: the exact count is not stable, and not interesting. What's stable is the shape. Double the input and the cost doubles. The cost of sum is a straight line in n.

Now the two-loop version of a real problem: does this array contain a duplicate?

function has_duplicate(items):
    for i from 0 to n-1:
        for j from i+1 to n-1:
            if items[i] == items[j]:
                return true
    return false

The inner loop runs about n times for each of the n outer iterations. Total comparisons: n(n-1)/2, which is roughly n²/2. Double the input and the cost quadruples. That's not a line, that's a parabola, and it's exactly the shape that ate GTA Online: do-something-per-item, where the something itself walks all the items.

The growth ladder

Two counts so far: 2n + 2 and n²/2. Big-O notation is the act of throwing away everything about those expressions except the shape.

We drop constant factors: 2n and n and 100n are all O(n). We drop lower-order terms: n² + 50n + 7 is O(n²), because as n grows, the n² term doesn't just win, it makes the others irrelevant. At n = 1,000, n² is a million and 50n is fifty thousand; at n = 1,000,000, n² is a trillion and 50n is a rounding error. Big-O answers one question only: when n gets large, how does cost grow?

That sounds like it throws away too much. Surely the difference between 2n and 100n matters? It does, sometimes, and we'll come back to exactly when. But first, the ladder. Almost every algorithm in this course lands on one of these rungs:

Abstract ladders don't build intuition, so let's price the rungs in wall time. A modern laptop core does on the order of 10⁸ simple operations per second in an interpreted language, more in a compiled one; 10⁸ is a usable round number. At n = 1,000,000:

Read that table again, because it's the whole argument. Between O(n) and O(n²) at a million items sits the difference between "ten milliseconds" and "nearly three hours". No compiler upgrade, no faster CPU, no rewrite-it-in-Rust closes a gap like that. Hardware buys you constant factors; the shape of the growth is fixed by the algorithm. That's why this is the first lesson of the course.

The strangest rung deserves a word: O(log n). Logarithmic cost appears whenever each step halves what's left. A million items takes about 20 halvings to get down to one (2²⁰ is just over a million). A billion takes 30. Growth so slow it barely registers as growth. Whenever a structure or algorithm in this course manages to halve its problem each step, you'll see log n appear in its price tag, and lesson 8, on binary search, is built entirely out of this one move.

Best, average, worst

Here's a wrinkle. Consider the simplest search there is:

function find(items, target):
    for i from 0 to n-1:
        if items[i] == target:
            return i
    return -1

What does this cost? It depends. If the target sits in slot 0, one comparison: O(1). If it's missing entirely, n comparisons. Same code, different inputs, costs that differ by a factor of a million. So "the cost of find" isn't one number; it's three.

The best case (target first) is trivia. Nobody plans around getting lucky. The worst case (target absent or last) is the number big-O quotes by convention, and the convention exists for a good reason: the worst case is a guarantee. When we say find is O(n), we're saying it never costs more than a pass through the array, and you can build systems on never. The average case asks what happens over typical or random inputs (for find, about n/2 comparisons, still O(n) once constants drop).

For most of this course, worst case is the only number we track. There's one giant exception coming: hash tables, in lesson 12, are beloved precisely because their average case is O(1) while their worst case is O(n), and engineering them is the art of making the worst case so rare you can price them at their average. File that away.

Amortized: the expensive operation that's secretly cheap

Now for the most misunderstood word in the lesson's title.

Some operations are occasionally expensive by design. The classic example, and the one you'll build with your own hands in lesson 3, is appending to a dynamic array (a list in Python, an Array in JavaScript, a slice in Go). The array owns a block of memory with some capacity. Appending into spare capacity costs O(1): write the value, bump the length. But when capacity runs out, the array allocates a new block twice the size and copies every element across. That append costs O(n).

So is append O(1) or O(n)? A pessimist quotes the worst case and says O(n). But watch what the doubling actually does. Start with capacity 1 and append 8 items: copies happen when capacity grows 1→2, 2→4, 4→8, costing 1 + 2 + 4 = 7 element-copies in total, on top of the 8 writes. Append a million items and total copies come to 1 + 2 + 4 + ... + 524,288, which is just under a million. The general fact: each doubling copies everything so far, but the doublings are spaced exponentially far apart, so all the copies ever performed sum to less than 2n. Total cost of n appends: under 3n steps. Spread across n operations, that's a constant ~3 steps each.

That spread-out price is the amortized cost: total cost of a sequence of operations divided by the number of operations. Dynamic array append is O(1) amortized, and that's a guarantee about the sum, not a probabilistic hope like an average case. A useful mental model: every cheap append deposits a couple of spare "step tokens" into a bank; the rare expensive copy withdraws the balance. The bank never overdrafts, so no sequence of appends can ever cost more than ~3n total. Any individual append might still be slow. Over any run of them, the structure is fast, by arithmetic, not luck.

Why this matters practically: when you see "O(1) amortized" on an operation, you can treat it as constant-time in your planning unless you're in a domain where a single slow operation is unacceptable (real-time audio, trading systems, a frame budget in a game). Then the spikes matter and you reach for structures with worst-case bounds. Knowing which situation you're in is the skill.

Space counts too

Everything so far priced time. Memory gets the same treatment: space complexity counts the extra memory an algorithm needs as a function of n, not counting the input itself.

The two duplicate-checkers make the trade concrete. The nested-loop version uses two index variables and nothing else: O(1) extra space, O(n²) time. t0st's hash-set fix remembers everything it has seen: O(n) extra space, O(n) time. Neither is free; they're trading different resources. The fix that saved GTA Online spent memory to buy time, which is the single most common trade in this course, and in production engineering generally.

The trade, in real code

The videos in this course stay in pseudocode so the ideas stay language-agnostic; the written companion is where real implementations live. Here is the O(n) time, O(n) space duplicate-checker, the same shape as t0st's fix, in the three languages this course carries.

function hasDuplicate(items: number[]): boolean {
  const seen = new Set<number>()
  for (const x of items) {
    if (seen.has(x)) return true
    seen.add(x)
  }
  return false
}

func hasDuplicate(items []int) bool {
	seen := make(map[int]struct{}, len(items))
	for _, x := range items {
		if _, ok := seen[x]; ok {
			return true
		}
		seen[x] = struct{}{}
	}
	return false
}

bool has_duplicate(const std::vector<int>& items) {
    std::unordered_set<int> seen;
    seen.reserve(items.size());
    for (int x : items) {
        if (seen.contains(x)) return true;
        seen.insert(x);
    }
    return false;
}

All three do the same thing per element: one membership check, one insert, each O(1) on average (the hash-table fine print behind that "on average" is lesson 12). One linear pass, O(n) time, O(n) extra space. Two details worth noticing: Go has no built-in set, so the idiom is a map with empty-struct values, which occupy zero bytes; and in Go and C++ we pre-size the container with len(items) / reserve, which avoids exactly the grow-and-copy cycles the amortized section described. The quadratic version needs no translation; it's the same two nested loops in any language, and it's just as slow in all of them.

One source of space cost hides from beginners: recursion. Every nested function call holds its local variables in a stack frame until it returns, so a function that recurses n levels deep is using O(n) memory even though no line of it ever allocates anything. Lesson 9 makes the call stack concrete, and from then on we price it like any other allocation.

Where the model lies

Time to break the promise the RAM model made. It assumed every memory access costs the same constant step. On real hardware that is false, and not slightly false: a read that hits the CPU's L1 cache costs around 1 nanosecond, while a read that misses every cache and goes to main memory costs around 100. Same instruction, two orders of magnitude apart, depending only on where the data is and what you touched before it.

The consequence: two algorithms with the same big-O can differ by 10x or more in practice, depending on whether they touch memory in an order the hardware likes. Big-O got us from three hours down to milliseconds in the GTA story; the memory hierarchy is what separates fast O(n) from slow O(n). This is also the honest answer to "when do constants matter": when n is small (real sorting libraries switch to a quadratic insertion sort below a couple dozen elements, because its constants are tiny) and when memory layout makes one algorithm's "step" physically cheaper than another's.

So the discipline of this course is: big-O first, always, because no constant factor survives the growth-ladder table. Then, with the shape settled, the machine gets a vote. The next lesson is about that vote: what caches actually do, why arrays are the hardware's favorite data structure, and why the humble contiguous block of memory beats theoretically fancier structures far more often than the textbooks suggest.