4.1 — Complexity: Reading the Cost of Code

Two engineers write the same feature: "given a list of orders, tell me which customer IDs appear more than once."

// Version A
function duplicatesA(customerIds: string[]): string[] {          // (1)
  const seen: string[] = [];                                     // (2)
  const dupes: string[] = [];
  for (const id of customerIds) {                                // (3)
    if (seen.includes(id)) dupes.push(id);                       // (4)
    else seen.push(id);
  }
  return dupes;
}

// Version B
function duplicatesB(customerIds: string[]): string[] {
  const seen = new Set<string>();                                // (5)
  const dupes: string[] = [];
  for (const id of customerIds) {
    if (seen.has(id)) dupes.push(id);                            // (6)
    else seen.add(id);
  }
  return dupes;
}

Line by line:

1. Both take an array of customer ID strings and return the IDs that showed up at least twice.
2. Version A remembers what it has already seen in a plain array. To ask "have I seen this?", an array has no choice but to walk itself from the front.
3. The loop visits each ID once. That part is identical in both versions.
4. seen.includes(id) is the expensive line. It scans the seen array from the beginning until it finds a match or runs out. If seen currently holds 40,000 items, this one line does up to 40,000 string comparisons.
5. Version B remembers with a Set, which is built on hashing (Chapter 4.3 takes this apart). A Set jumps more or less straight to the right spot instead of scanning.
6. seen.has(id) does a small, roughly fixed amount of work no matter how many items are already in the set.

On 1,000 orders both finish instantly and you cannot tell them apart. On 100,000 orders, version B still finishes in a few milliseconds, and version A takes about five billion string comparisons and hangs the request. Nobody wrote a bug. The difference is entirely in how the cost of each version grows as the input grows.

Complexity analysis is the vocabulary for talking about that growth precisely, before you have any data, on a whiteboard, with no profiler. This chapter builds it from counting operations by hand up to solving the recurrences that describe merge sort and quicksort, and it spends most of its length on the analyses that people actually get wrong, because those are the ones interviewers ask about and the ones that bite in production.

1. Count the operations, then throw most of the count away

Start literally. Here is a function and a count.

function sumFirstK(values: number[], k: number): number {   // (1)
  let total = 0;                                            // (2)  1 operation
  for (let i = 0; i < k; i++) {                             // (3)  k+1 comparisons, k increments
    total += values[i];                                     // (4)  k reads, k additions, k assignments
  }
  return total;                                             // (5)  1 operation
}

Adding those up honestly: roughly 1 + (k + 1) + k + 3k + 1, which is 5k + 3 "operations", where "operation" means something the CPU does in a small fixed amount of time.

Now the two moves that turn that arithmetic into something useful.

Move one: drop the constant multiplier. The 5 in 5k + 3 is not a real number. It depends on the language, the compiler, whether the array is in cache (Chapter 1.6), and what the CPU had for breakfast. Another machine gives you 11k + 3. The 5 is noise, but the fact that the count is proportional to k is not noise. That survives every machine, every language, forever.

Move two: drop everything except the fastest-growing term. In 5k + 3, the +3 matters when k is 2 and is invisible when k is a million. In n² + 500n, the 500n term looks bigger up to n = 500 and then never matters again. Since complexity is a statement about what happens as the input gets large, only the biggest term survives.

Apply both moves to 5k + 3 and you get k. We write this O(k) and say "order k" or "linear in k".

Why we care about large inputs and not small ones

Because small inputs are never the problem. No algorithm is too slow on 10 items. The reason to analyse growth is to answer "what happens when this succeeds and we have a million users", and that question has a clean mathematical answer while "how many milliseconds" does not.

2. Big-O, Big-Omega and Big-Theta, said plainly

Chapter 1.6 gave big-O a working definition so cache analysis could use it. Here is the full family, and the honest note about how the industry actually uses the words.

Big-O — the ceiling. f(n) = O(g(n)) means: past some input size, f never grows faster than a constant multiple of g. Formally, there exist constants c > 0 and n_0 such that f(n) \le c \cdot g(n) for all n \ge n_0. In English: "grows no faster than."

The two constants are what make the definition work. c absorbs the machine-dependent multiplier we threw away in move one. n_0 absorbs the small inputs where the lower-order terms still dominate, so you are allowed to ignore the awkward beginning of the curve.

Big-Omega — the floor. f(n) = \Omega(g(n)) means f grows at least as fast as g: there exist c > 0, n_0 with f(n) \ge c \cdot g(n) for n \ge n_0. In English: "grows no slower than."

Big-Theta — the sandwich. f(n) = \Theta(g(n)) means both at once, so g describes the growth exactly, up to a constant: c_1 g(n) \le f(n) \le c_2 g(n).

Look at the two loops below to see why three words are needed instead of one.

function containsZero(values: number[]): boolean {   // (1)
  for (const v of values) {
    if (v === 0) return true;                        // (2)  may exit on the first item
  }
  return false;                                      // (3)  or walk the whole array
}

1. The function scans for a zero.
2. If values[0] is zero it returns after one comparison. So the best case is a fixed amount of work.
3. If there is no zero at all it touches every element, so the worst case is proportional to n.

The honest statements are: worst case \Theta(n), best case \Theta(1), and — covering both — the running time is O(n) and \Omega(1). There is no single \Theta for the function as a whole, because its cost genuinely depends on the input, not just on the input size.

The industry convention you must know. In interviews and in most writing, when someone says "this is O(n \log n)" they mean "the worst case is \Theta(n \log n)" — they are using O where \Theta is technically meant. It is sloppy and it is universal. Saying "binary search is O(n^{100})" is true (a ceiling that loose is still a ceiling) and will still get you a strange look, because everyone reads O as "tight". Use O the way everyone else does, but know what it actually means, because "is O an upper bound on the worst case or the average case?" is a real interview question and the answer is: O is a bound on a function, and you have to say which function — worst case, best case or average case. They are three different functions.

3. The growth ladder, with numbers attached

Names are not intuition. Here is what each growth rate does to a real workload. Assume one operation takes 1 nanosecond, which is roughly right for a simple operation on a modern CPU.

Growth	Name	n = 1,000	n = 1,000,000	Feels like
O(1)	constant	1 ns	1 ns	instant
O(\log n)	logarithmic	10 ns	20 ns	instant
O(n)	linear	1 µs	1 ms	fine
O(n \log n)	linearithmic	10 µs	20 ms	fine
O(n^2)	quadratic	1 ms	17 minutes	dies at scale
O(n^3)	cubic	1 s	31 years	dies early
O(2^n)	exponential	heat death	heat death	n must stay tiny
O(n!)	factorial	heat death	heat death	n under ~11

Three things to take from the table.

The cliff is between n \log n and n^2. Everything above the line scales to real data. Everything below it has a ceiling you will hit. That is why so much of algorithm work is "I found an n^2 solution, now can I get it to n \log n".

O(\log n) is nearly free. Doubling the input adds one step. Going from a thousand items to a million items takes binary search from about 10 steps to about 20. This is why sorted structures and balanced trees are everywhere.

Exponential is not "slow", it is "impossible". 2^{100} is larger than the number of atoms in the observable universe. When your analysis lands on O(2^n), the answer is never "buy a faster machine", it is "find a different algorithm, or accept that n stays under 30" (Chapter 4.29 covers what to do when the problem itself is genuinely exponential).

What is a logarithm, in one paragraph

\log_2 n is "how many times do I halve n before I reach 1". Halve 1,000: 500, 250, 125, 62, 31, 15, 7, 3, 1 — nine or ten halvings, so \log_2 1000 \approx 10. That is the whole idea, and it is why any algorithm that repeatedly throws away half the remaining work is logarithmic. In complexity we almost never write the base, because changing the base only multiplies by a constant (\log_2 n = \log_{10} n / \log_{10} 2), and constants get dropped. Chapter 1.8 develops logarithms further for information theory.

4. The mechanical rules for reading code

You can compute the complexity of most code with four rules and no cleverness.

Rule 1 — sequential blocks add, so the biggest wins. Code that sorts an array (n \log n) and then scans it once (n) costs n \log n + n, which is O(n \log n). Adding a linear pass to a sort is free in complexity terms.

Rule 2 — nested loops multiply. A loop of n containing a loop of m is O(nm). If both run over the same array, O(n^2).

Rule 3 — the loop bound is what matters, not the loop shape. These are all O(n): for (i = 0; i < n; i++), for (i = n; i > 0; i--), for (i = 0; i < n; i += 3). Stepping by 3 does n/3 iterations, and 1/3 is a constant.

Rule 4 — multiplying or dividing the counter gives a log. for (i = 1; i < n; i *= 2) runs \log_2 n times, because i goes 1, 2, 4, 8, 16 and reaches n after about \log_2 n doublings.

Now the case that catches almost everyone:

function trianglePairs(items: string[]): [string, string][] {  // (1)
  const pairs: [string, string][] = [];
  for (let i = 0; i < items.length; i++) {                     // (2)
    for (let j = i + 1; j < items.length; j++) {               // (3)  ← starts at i+1, not 0
      pairs.push([items[i], items[j]]);
    }
  }
  return pairs;
}

1. This builds every unordered pair — useful for "compare every item to every other item once".
2. The outer loop runs n times.
3. The inner loop runs n−1 times, then n−2, then n−3, down to 1.

The total is (n-1) + (n-2) + \dots + 1 = \frac{n(n-1)}{2}, which expands to \frac{n^2}{2} - \frac{n}{2}. Drop the constant multiplier and the lower term, and it is O(n^2).

The trap is believing that "only half the pairs" makes it faster than quadratic. It does not. Halving is a constant factor, and constants are exactly what big-O deletes. A "half" triangle loop and a full double loop are both O(n^2) and both die at the same input size — one just dies a couple of seconds later.

The complementary trap, going the other way:

for (let i = 0; i < n; i++) {
  for (let j = 0; j < 100; j++) {   // ← inner bound does NOT depend on n
    doSomething(i, j);
  }
}

This looks nested and quadratic. It is O(n), because the inner loop does a fixed 100 iterations regardless of input size, and 100 is a constant. The question is never "is it nested", it is "does the inner bound grow with the input".

5. The costs hiding inside library calls

The most common analysis mistake in real code is treating a library call as if it were free. It is not; it has its own complexity, and when you put it inside a loop you multiply by it.

// A real bug from a reporting endpoint
function buildReport(rows: Row[]): string {
  let out = '';                                    // (1)
  for (const row of rows) {
    out += row.id + ',' + row.total + '\n';        // (2)  ← the bug
  }
  return out;
}

1. Start with an empty string.
2. Strings in JavaScript, Python, Java and C# are immutable, meaning a string's characters can never be changed in place. So out += ... does not append. It allocates a brand new string, copies every character of the old one into it, then copies the new piece on the end.

By the time you are on row 50,000, each += copies about 50,000 rows' worth of characters. Summing over all rows gives the same triangle as before: O(n^2) character copies for what looks like a single linear loop. The fix is to collect the pieces and join once, which copies each character exactly once:

function buildReportFixed(rows: Row[]): string {
  const parts: string[] = [];                            // (1)
  for (const row of rows) parts.push(`${row.id},${row.total}`);  // (2)  O(1) each
  return parts.join('\n');                               // (3)  O(total characters), once
}

1. Collect into an array instead of a string.
2. push appends to the end of a dynamic array, which is O(1) on average (Chapter 4.2 explains why "on average", and section 7 below proves it).
3. join walks the parts once and copies each character once. Total: O(n).

Here is the reference table of hidden costs. Memorise this one; it is what turns "looks fine" into "will not scale".

Call	Cost	Why
arr.includes(x), indexOf	O(n)	scans from the front
arr.push(x)	O(1) average	see section 7
arr.unshift(x), shift()	O(n)	every element shifts one slot
arr.splice(i, 1)	O(n)	closes the gap by shifting
arr.slice(a, b)	O(b-a)	copies the range
arr.sort()	O(n \log n)	comparison sort
set.has(x), map.get(k)	O(1) average	hashing, Chapter 4.3
str + str	O(\text{len})	copies both
Object.keys(o)	O(n)	builds a new array
str.substring(a,b)	O(b-a)	copies (in most engines)

The dangerous rows are includes, unshift, shift and splice, because each is a single innocent line that turns the loop containing it from O(n) into O(n^2). A linear operation inside a linear loop is quadratic, and that sentence explains a very large share of real production slowdowns.

6. Space complexity, and the part people forget

Space complexity counts memory the same way time complexity counts operations: how does the extra memory used grow with the input?

The convention is to count auxiliary space — what your algorithm allocates on top of the input it was handed. Reversing an array in place is O(1) auxiliary space (a couple of index variables) even though the array itself is n items long, because you did not allocate the array.

The part people forget is the call stack. Every pending recursive call holds a frame with its parameters and local variables (Chapter 2.2 covers the stack; Chapter 3.4 covers frames per language). So a recursion that goes d levels deep before returning uses O(d) space, whether or not you allocated anything yourself.

function sumTree(node: TreeNode | null): number {   // (1)
  if (node === null) return 0;                      // (2)
  return node.value + sumTree(node.left) + sumTree(node.right);  // (3)
}

1. Sum every value in a binary tree.
2. The base case: an empty branch contributes nothing.
3. Each call waits for two child calls to return, so its frame stays on the stack while they run.

Time is O(n) — each node is visited once. Space is O(h) where h is the height of the tree, because at any moment the stack holds one frame per level from the root down to wherever you currently are. For a balanced tree h \approx \log n, so the space is tiny. For a degenerate tree that is one long chain, h = n, the stack holds n frames, and on a deep enough tree you get a stack overflow crash. "What is the space complexity?" almost always means "how deep does the recursion go?" and answering with the depth rather than "O(1), I did not allocate anything" is the difference between a correct and an incorrect answer.

7. Amortized analysis: why push is O(1) when it sometimes copies everything

A dynamic array (JavaScript's Array, Python's list, C++'s vector) is a fixed-size block of memory with a count of how many slots are used. When you push into a full block, it cannot grow in place — something else may be sitting right after it in memory. So it allocates a bigger block, copies everything across, and frees the old one.

That copy is O(n). So how can anyone claim push is O(1)?

The trick is that the array does not grow by one slot. It grows by doubling. Watch the total copying cost of n pushes when capacity starts at 1:

push 1  → capacity 1 → 2, copy 1 item
push 2  → capacity 2 → 4, copy 2 items
push 4  → capacity 4 → 8, copy 4 items
push 8  → capacity 8 → 16, copy 8 items
...
push n/2 → copy n/2 items

Total copies: 1 + 2 + 4 + 8 + \dots + n/2. That sum is famously just under n — every doubling series sums to about twice its largest term, and here the largest term is n/2. So n pushes cost about n copies in total, which is 1 copy per push on average.

Amortized complexity is exactly this: the average cost per operation across a whole sequence of operations, when an occasional expensive operation is paid for by many cheap ones. Push is O(1) amortized and O(n) worst case for a single call, and both statements are true at once.

Why doubling and not "grow by 100 slots"? If you grow by a fixed 100 slots, you resize n/100 times, and resize number k copies 100k items. Summing gives 100 \cdot (1 + 2 + \dots + n/100), the triangle again, so O(n^2) total and O(n) amortized per push. Growing by a multiplier is what makes the series shrink geometrically; growing by a constant does not. Real engines use factors between 1.5 and 2 — the smaller factor wastes less memory and lets freed blocks be reused, the larger factor resizes less often.

Where amortized reasoning breaks. If a single operation must finish inside a hard deadline — a game frame, an audio buffer, a control loop — the amortized average is cold comfort, because that one push that copies 4 million items will blow the deadline. In those systems people pre-allocate capacity up front precisely to make the worst case equal the average case.

8. Recurrences and the Master theorem: analysing divide and conquer

Loops you can count. Recursive algorithms that split their input need a different tool, because the cost is defined in terms of itself.

Merge sort splits the array in half, sorts each half by calling itself, then merges the two sorted halves in one linear pass. Write that as an equation, where T(n) means "the time to run on an input of size n":

T(n) = 2\,T(n/2) + \Theta(n)

Read it out loud: two subproblems, each of size n/2, plus n work to combine them. That is a recurrence relation. Solving it means finding a closed form for T(n).

Method one: draw the recursion tree. This is the method to use in an interview, because it is visual and hard to get wrong.

Merge sort's recursion tree. Going down a level doubles the number of pieces and halves each piece's size, so the work on every level is exactly n. The depth is the number of halvings needed to reach size 1, which is log₂ n. Total = n per level × log₂ n levels = n log n.

The figure is the whole proof. Level 0 does n work. Level 1 has two pieces of size n/2, totalling n. Level 2 has four pieces of size n/4, totalling n. Every level totals n. The tree bottoms out when the pieces reach size 1, which takes \log_2 n halvings. So the total is n \times \log_2 n, and merge sort is \Theta(n \log n).

Method two: the Master theorem. This is a lookup table for recurrences of the shape

T(n) = a\,T(n/b) + f(n)

where a \ge 1 is how many subproblems you make, b > 1 is the factor you shrink by, and f(n) is the work you do outside the recursive calls (splitting plus combining).

The whole theorem is a race between two quantities: the work at the leaves of the tree, which is n^{\log_b a}, and the work at the root, which is f(n). Whichever wins dominates the total.

Case 1 — the leaves win. If f(n) grows slower than n^{\log_b a}, then T(n) = \Theta(n^{\log_b a}). Case 2 — it is a tie. If f(n) = \Theta(n^{\log_b a}), every level does the same work, so multiply by the number of levels: T(n) = \Theta(n^{\log_b a} \log n). Case 3 — the root wins. If f(n) grows faster than n^{\log_b a} (and satisfies a regularity condition that holds for every function you will meet in practice), then T(n) = \Theta(f(n)).

Worked on merge sort: a = 2, b = 2, f(n) = n. Compute n^{\log_b a} = n^{\log_2 2} = n^1 = n. That equals f(n), so it is case 2, and T(n) = \Theta(n \log n). Same answer as the tree, in three lines.

Three more you should be able to do on sight:

Recurrence	a, b, f(n)	n^{\log_b a}	Case	Answer
T(n)=T(n/2)+\Theta(1)	1, 2, 1	n^0 = 1	tie	\Theta(\log n)
T(n)=2T(n/2)+\Theta(1)	2, 2, 1	n	leaves	\Theta(n)
T(n)=T(n/2)+\Theta(n)	1, 2, n	1	root	\Theta(n)

Row one is binary search: one subproblem, half the size, constant work to pick a side. Row two is traversing a balanced binary tree: two subproblems, half the size each, constant work per node — and the answer confirms what you already knew, that visiting every node is linear. Row three is the surprising one: it is quickselect, which partitions the array (that is the \Theta(n)) and then recurses into only one side. The linear partition at the root dominates everything below it, so finding the k-th smallest element is linear, not n \log n. The sum n + n/2 + n/4 + \dots converges to 2n, and that is the whole reason.

When the Master theorem does not apply. It needs equal-sized subproblems. T(n) = T(n-1) + \Theta(1) — one subproblem one smaller, not one half the size — is not of the right shape. Expand it by hand instead: T(n) = T(n-1) + 1 = T(n-2) + 2 = \dots = \Theta(n). Likewise T(n) = 2T(n-1) + \Theta(1) doubles the number of calls each time you go one level down, giving \Theta(2^n) — that is the naive recursive Fibonacci, and it is why Chapter 4.22 exists.

9. The analyses people get wrong

These are the ones worth slowing down on, because each has a plausible wrong answer that sounds right.

Building a heap is O(n), not O(n \log n). Inserting n items one at a time into a heap costs O(n \log n), and that is the answer most people give. But heapify — the bottom-up build — costs O(n). The reason is that the expensive sift-down operation is only expensive for nodes near the top, and a heap has almost no nodes near the top. Half of all nodes are leaves and cost zero, a quarter are one level up and cost at most one swap, an eighth cost at most two. Summing \sum_{h} \frac{n}{2^{h+1}} \cdot h gives a series that converges to 2n. The rule to remember: when most of the nodes are cheap, do not multiply the worst-case node cost by the node count. Chapter 4.16 builds this.

Two sequential loops are not O(n^2). Sequential means add. Only nesting multiplies. for(...n...){} for(...n...){} is O(n).

for (i...n) for (j...i) is quadratic even though it "does less". Section 4 covered this. Half of a square is still a square in growth terms.

Sorting inside a loop.

for (const user of users) {          // n iterations
  const top = user.scores.sort((a, b) => b - a)[0];   // ← m log m each time
}

If every user has m scores, this is O(n \cdot m \log m), and you did not need a sort at all — you needed the maximum, which is O(m). Reaching for sort when you want one element is one of the most common real-world quadratic-ish mistakes.

Recursion with an array copy in it.

function permutations(rest: number[], acc: number[] = []): number[][] {
  if (rest.length === 0) return [acc];
  return rest.flatMap((v, i) =>
    permutations([...rest.slice(0, i), ...rest.slice(i + 1)], [...acc, v]));  // ← copies
}

The recursion generates n! permutations, so it can never be better than O(n!). But each call also copies two arrays of length up to n, so the true cost is O(n \cdot n!). This matters when you compare it to the backtracking version in Chapter 4.18, which mutates one shared array and undoes the change on the way out, cutting the copying entirely. Whenever you see spread syntax or slice inside a recursive call, add the copy cost to the analysis.

Two different inputs need two different letters. If a function takes an array of n users and an array of m orders and loops one inside the other, the answer is O(nm) and not O(n^2). Writing O(n^2) when there are two independent inputs is a specific thing interviewers listen for, because O(nm) with n = 10 and m = 1,000,000 behaves nothing like a square.

Amortized is not average-case. They get confused constantly. Amortized is about a sequence of operations on one structure, and it is a guarantee: any n pushes cost O(n) total, full stop, no assumptions. Average case is about the distribution of inputs, and it is an assumption: hash lookup is O(1) on average if the keys hash reasonably, and an attacker who chooses colliding keys can make it O(n) (Chapter 4.3 covers that attack). Amortized cannot be defeated by an adversary. Average case can.

10. Where the model lies to you

Big-O assumes every basic operation costs the same. Chapter 1.6 already showed that this is false: reading a value that is in L1 cache takes about 1 nanosecond, and reading one from main memory takes about 100 nanoseconds. Big-O counts both as "1".

That gap is why a linked list with O(1) insertion frequently loses to an array with O(n) insertion on real hardware for anything under a few thousand elements. The array's elements sit next to each other in memory, so the CPU's prefetcher fetches the next ones before you ask (Chapter 1.6 calls this spatial locality). The linked list's nodes are scattered, so every next pointer is a cache miss. The array does more operations, and each one is up to a hundred times cheaper.

The second lie is that constants do not matter. They do not matter asymptotically, and they matter enormously at the sizes real code sees. This is why real sort implementations switch to insertion sort for small subarrays — insertion sort is O(n^2) and it beats O(n \log n) merge sort below roughly 16 elements, because its constant factor is tiny and it has no allocation. Chapter 4.10 covers Timsort and introsort, which are both built on exactly this compromise.

So the honest workflow is: use complexity to rule out designs before you build them, because it is right about the shape of the curve and it is free to compute; then measure, because it is silent about the multiplier. Anyone who only does the first has algorithms that are asymptotically perfect and slow. Anyone who only does the second ships an O(n^2) endpoint that passes staging with 100 rows and dies in production with 100,000.

What the interviewer will push on

"You said O(n). What is n?" They are checking that you know complexity is measured against a named input size, not a vibe. If the input is a string, is n the length? If it is a grid, is n the cells or the side length? A grid answer of O(n^2) where n is the side length and O(n) where n is the number of cells are the same algorithm. Name your variable before you give the answer: "let n be the number of nodes and m the number of edges". Missing this is the single most common way a correct analysis gets marked wrong.

"Is that worst case or average?" The tell for real understanding is naming both and saying what makes them differ. Quicksort: \Theta(n \log n) average, \Theta(n^2) worst case when the pivot is always the smallest remaining element, which happens on already-sorted input with a first-element pivot — and randomising the pivot makes the bad case require an adversary who can predict your random numbers rather than merely sorted data. The wrong answer is "quicksort is O(n \log n)", full stop.

"What is the space complexity?" The common wrong answer is O(1) for anything that does not obviously allocate. Check three places: the output you build, the recursion depth, and any copy your library calls make. Merge sort's answer is O(n) auxiliary and that is exactly why in-place quicksort is often preferred despite the worse worst case.

"Can you do better?" They are checking whether you know the lower bound, which is a different question from optimising your code. Any comparison-based sort needs \Omega(n \log n) comparisons, so if you have an n \log n sort, "no, not with comparisons" is the correct and complete answer — and the follow-up is that counting sort beats it by not comparing, at the cost of needing a bounded key range. Similarly, any algorithm that must look at every input element is \Omega(n), so if you are at O(n) you can stop.

"You said this is amortized O(1) — when would that not be good enough?" Real answer: when a single slow operation violates a deadline. Frame rendering, audio processing, a trading system's hot path. The fix is to pre-size the structure so the resize never happens during the critical window.

One thing to volunteer: say out loud which term you dropped and why it is safe to drop. "This is O(n \log n + m); I am keeping the m separate because the two inputs are independent and m can be much larger." That one sentence signals you are computing rather than pattern-matching, and it is the difference between reciting a complexity and deriving one.

Recall

• Big-O is an upper bound on a stated function (worst, best or average case) — the industry uses it to mean a tight worst-case bound, which is really Big-Theta.
• Drop constant multipliers and lower-order terms; keep the fastest-growing term. Sequential blocks add, nested loops multiply, and a loop bound that does not grow with the input is a constant.
• A linear library call (includes, shift, splice, string +=) inside a linear loop makes the whole thing O(n^2) — this is the most common real slowdown.
• Amortized O(1) means n operations cost O(n) total, guaranteed; it comes from geometric growth, and it is not the same as average case, which is an assumption about inputs an adversary can break.
• Divide and conquer is read off the recursion tree (work per level × number of levels) or the Master theorem T(n)=aT(n/b)+f(n), which is a race between the leaves at n^{\log_b a} and the root at f(n).
• Space complexity includes the call stack: recursion of depth d costs O(d) even if it allocates nothing.

Self-test: Why is for (j = i+1; j < n; j++) inside a loop over n still quadratic? · Why is push O(1) amortized but O(n) in the worst case, and what breaks if the array grows by a fixed 100 slots instead of doubling? · Solve T(n) = T(n/2) + \Theta(n) and explain why the answer is not \Theta(n \log n). · A function takes an n-element array and an m-element array and nests one loop in the other — what is the complexity, and why is O(n^2) wrong? · Why does an array with O(n) insertion often beat a linked list with O(1) insertion in practice?

Next: 4.2 takes the array apart — how a contiguous block of memory turns into a growable list, why the growth factor is a real engineering decision, and how string immutability shapes every text-processing algorithm you will write.