Complexity tables

Every cost in the course, in one place. Written to be printed — the header, footer and controls drop out when you do.

Two things are worth saying before the numbers. First, complexity describes how cost grows, not how fast something is; an O(n²) algorithm can beat an O(n log n) one on small input, and often does. Second, in an interview you should state both time and space without being asked. Volunteering “this is O(n log n) time and O(n) space because the merge needs a buffer” reads as fluency in a way that answering the question afterwards does not.

Growth rates

How fast each class of algorithm grows. Assume roughly 10⁸ simple operations per second.
Complexity	n = 10	n = 1,000	n = 100,000	n = 10,000,000	Verdict
`O(1)`	1	1	1	1	Instant, always
`O(log n)`	3	10	17	23	Instant, always
`O(n)`	10	1,000	100,000	10,000,000	Fine
`O(n log n)`	33	10,000	1.7 million	230 million	Fine, the sorting bound
`O(n²)`	100	1 million	10 billion	—	Fine to about n = 10,000
`O(n³)`	1,000	1 billion	—	—	Only to about n = 500
`O(2ⁿ)`	1,024	—	—	—	Only to about n = 25
`O(n!)`	3.6 million	—	—	—	Only to about n = 11

Reading the constraints

The problem statement usually tells you the intended complexity, if you know how to look. This table is the single most useful thing on this page during a timed interview.

Read the constraints backwards: the size of n tells you which complexity is being asked for.
If n is up to	The intended solution is probably	Which usually means
10–12	`O(n!)`	Permutations, brute-force ordering
15–20	`O(2ⁿ)` or `O(2ⁿ × n)`	Subsets, bitmask DP, travelling-salesman shapes
100	`O(n³)`	Floyd–Warshall, interval DP, triple loops
1,000–5,000	`O(n²)`	Two-sequence DP, all-pairs comparison
10⁵ to 10⁶	`O(n log n)`	Sorting, heaps, binary search on the answer
10⁷ and above	`O(n)` or `O(log n)`	One pass, two pointers, sliding window, hashing, maths

Arrays

Arrays. The three marked in red are the ones that quietly turn a linear algorithm quadratic.
Operation	Cost	Note
`arr[i]` read or write	`O(1)`	Direct index arithmetic
`push` / `pop`	`O(1)`	Amortised; an occasional resize is `O(n)`
`shift` / `unshift`	`O(n)`	Every element moves. Use an index or a deque instead
`splice(i, k)`	`O(n)`	Shifts the tail
`slice` / spread `[...a]`	`O(n)`	A copy. Innocuous-looking inside a loop, and fatal
`indexOf` / `includes`	`O(n)`	Use a `Set` if you do this repeatedly
`sort`	`O(n log n)`	Mutates in place, and stable since ES2019
`concat` / `join` / `map` / `filter`	`O(n)`	Each allocates a new array or string
`reverse`	`O(n)`	In place
`new Array(n).fill(x)`	`O(n)`	The standard way to preallocate

shift() versus a head index

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30// The same BFS, two ways. Count the work each one does.
function bfsShift(n) {
  const queue = [0];
  let steps = 0, seen = 1;
  while (queue.length) {
    const node = queue.shift();       // O(n): every remaining element moves
    steps += queue.length + 1;         // the shift itself costs this much
    if (seen < n) { queue.push(seen++); queue.push(seen++); }
  }
  return steps;
}

function bfsIndex(n) {
  const queue = [0];
  let steps = 0, seen = 1, head = 0;
  while (head < queue.length) {
    head++;                            // O(1): nothing moves
    steps += 1;
    if (seen < n) { queue.push(seen++); queue.push(seen++); }
  }
  return steps;
}

console.log('  n     shift()      head index     ratio');
for (const n of [100, 400, 1600]) {
  const a = bfsShift(n), b = bfsIndex(n);
  console.log(String(n).padStart(4), String(a).padStart(11), String(b).padStart(14), (a / b).toFixed(1).padStart(9) + 'x');
}
console.log('\nThe ratio grows in step with n: quadruple n, quadruple the ratio.');
console.log('That is the extra factor of n that shift() smuggles in.');

Output

Maps, sets and objects

Maps, Sets and objects. Average case; hashing has a real constant factor.
Operation	Map / Set	Plain object	Note
Insert	`O(1)`	`O(1)`	Average. Worst case is `O(n)` under adversarial keys
Lookup	`O(1)`	`O(1)`	`Map.get` versus `obj[key]`
Delete	`O(1)`	`O(1)`	`delete obj[k]` can deoptimise the object
Size	`O(1)`	`O(n)`	`map.size` is stored; `Object.keys(o).length` builds an array
Iterate	`O(n)`	`O(n)`	`Map` preserves insertion order; object keys reorder integer-like keys
Any key type	Yes	Strings and symbols only	Object keys are coerced to strings, so `1` and `'1'` collide

Strings

Strings. They are immutable, which is the source of every surprise here.
Operation	Cost	Note
`s[i]` / `charCodeAt`	`O(1)`
`s.length`	`O(1)`	Counts UTF-16 units, not characters
`+=` in a loop	`O(n)` amortised	Engines optimise this with ropes; still prefer an array and `join`
`slice` / `substring`	`O(k)`	Allocates. Inside a loop this is the hidden factor
`split` / `join`	`O(n)`
`indexOf` / `includes`	`O(n × m)` worst case	Not the linear-time algorithm you might assume
`localeCompare`	`O(n)`	Far slower than `<`; only use it when you need collation
Concatenating in a nested loop	`O(n³)`	The classic accidental cubic. See lesson 03

Data structures side by side

The structures, and what each one is actually for.
Structure	Access	Search	Insert	Delete	Space
Array (by index)	`O(1)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Dynamic array (at end)	`O(1)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Singly linked list	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Stack / Queue	`O(n)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Deque	`O(1)`	`O(n)`	`O(1)`	`O(1)`	`O(n)`
Hash map / set	—	`O(1)`	`O(1)`	`O(1)`	`O(n)`
Binary heap	`O(1)` peek	`O(n)`	`O(log n)`	`O(log n)` pop	`O(n)`
Balanced BST	`O(log n)`	`O(log n)`	`O(log n)`	`O(log n)`	`O(n)`
Degenerate BST	`O(n)`	`O(n)`	`O(n)`	`O(n)`	`O(n)`
Trie	—	`O(len)`	`O(len)`	`O(len)`	`O(total chars)`
Union-find	—	`O(α(n))`	`O(α(n))`	—	`O(n)`

Sorting

Sorting. Know merge sort and quicksort well enough to write them; know the rest well enough to name them.
Algorithm	Best	Average	Worst	Space	Stable?
Merge sort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Yes
Quicksort	`O(n log n)`	`O(n log n)`	`O(n²)`	`O(log n)`	No
Heapsort	`O(n log n)`	`O(n log n)`	`O(n log n)`	`O(1)`	No
Insertion sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes
Selection sort	`O(n²)`	`O(n²)`	`O(n²)`	`O(1)`	No
Bubble sort	`O(n)`	`O(n²)`	`O(n²)`	`O(1)`	Yes
Counting sort	`O(n + k)`	`O(n + k)`	`O(n + k)`	`O(k)`	Yes
Radix sort	`O(d(n + k))`	`O(d(n + k))`	`O(d(n + k))`	`O(n + k)`	Yes
`Array.prototype.sort`	`O(n)`	`O(n log n)`	`O(n log n)`	`O(n)`	Yes

Graph algorithms

Graph algorithms. V is vertices, E is edges.
Algorithm	Time	Space	What it answers
BFS	`O(V + E)`	`O(V)`	Shortest path when every edge costs the same
DFS	`O(V + E)`	`O(V)`	Reachability, cycles, components, ordering
Topological sort (Kahn)	`O(V + E)`	`O(V)`	A valid dependency order, or detects a cycle
Union-find over E edges	`O(E α(V))`	`O(V)`	Connectivity as edges arrive
Dijkstra (binary heap)	`O(E log V)`	`O(V + E)`	Cheapest paths, non-negative weights only
Bellman–Ford	`O(V × E)`	`O(V)`	Cheapest paths with negative edges; detects negative cycles
Floyd–Warshall	`O(V³)`	`O(V²)`	All pairs at once. Fine for V up to a few hundred
Kruskal / Prim	`O(E log V)`	`O(V + E)`	Minimum spanning tree
Adjacency list	—	`O(V + E)`	The default. Iterating a vertex's neighbours is `O(degree)`
Adjacency matrix	—	`O(V²)`	`O(1)` edge lookup, wasteful unless the graph is dense

Patterns

The patterns, and what each one costs.
Pattern	Time	Space
Two pointers	`O(n)`, or `O(n log n)` if you sort first	`O(1)`
Sliding window	`O(n)`	`O(k)`
Prefix sums	`O(n)` build, `O(1)` per query	`O(n)`
Hash map counting	`O(n)`	`O(n)`
Binary search on an array	`O(log n)`	`O(1)`
Binary search on the answer	`O(n log(range))`	`O(1)`
Monotonic stack	`O(n)` amortised	`O(n)`
Top-k with a capped heap	`O(n log k)`	`O(k)`
Tree DFS	`O(n)`	`O(h)`
Tree / graph BFS	`O(n)` or `O(V + E)`	`O(width)`
Backtracking, subsets	`O(n × 2ⁿ)`	`O(n)` plus output
Backtracking, permutations	`O(n × n!)`	`O(n)` plus output
1D dynamic programming	`O(n × choices)`	`O(n)`, often `O(1)`
2D dynamic programming	`O(mn)`	`O(mn)`, often `O(min(m,n))`
Bitmask DP	`O(2ⁿ × n)`	`O(2ⁿ)`

Space complexity, counted honestly

Space is the half candidates forget, and interviewers ask about it precisely because it separates people who have thought about the solution from people who have recalled it.

Output does not count, by convention. Returning 2ⁿ subsets is not O(2ⁿ) auxiliary space, though say so explicitly rather than leaving it ambiguous.
Recursion counts. A recursive tree traversal is O(h) space — O(log n) balanced, O(n) in the degenerate case. This is the most commonly missed answer.
Sorting counts. JavaScript's sort is not in-place in the O(1) sense; treat it as O(n).
Copies count. [...arr], slice, map and filter each allocate. One of them inside a loop is a hidden factor of n.
The alphabet is often constant. A 26-letter count array is O(1), not O(n). Saying that shows precision.

What to say out loud

A complete answer has four parts, and it takes about fifteen seconds.

Time, with the reason. “O(n log n), dominated by the sort; the sweep afterwards is linear.”
Space, with the reason. “O(n) for the hash map, or O(1) if I sort in place instead.”
Whether it fits. “With n up to 10⁵ that is about two million operations, so it is comfortable.”
The trade-off you chose. “I could drop to O(1) space by sorting, but that loses the original indices, which this problem needs.”

That last point is what separates a good answer from a complete one. Interviewers are listening for evidence that you know your solution sits on a spectrum, and that you picked a point on it deliberately.