Part 0 · 5 chapters · ~30 min
Why Algorithms, In A Frontend Course
A UI's sizes are small enough that linear work is free and large enough that quadratic work drops frames, and the line between them is one table. This part is the numbers to carry, four quadratics measured on a real table with their one-line fixes, the eight data structures that turn scans into lookups, how to measure the exponent in a minute, and the map of the course.
1
Where complexity bites in an interface
the question
"We never have a million of anything. Why would big-O matter in a UI?"
Because the frame budget is small and the sizes are not that small. A UI has thousands of DOM nodes, tens of thousands of records, and a budget of about ten million trivial operations per frame on a mid-range device. Linear work at those sizes is free; quadratic work crosses the budget at about three thousand items, which is one modest table. Most "the page freezes when the list gets big" bugs are an O(n²) step hiding in an innocent-looking loop, and most of them have a one-line fix: replace the scan inside the loop with a lookup.
the numbers to carry
- A frame: 16.7 ms at 60 Hz; the browser needs some of it; your budget is roughly 10 ms, or about 10 million trivial operations (one nanosecond each, optimised). On a low-end phone, divide by four.
- An interaction: 200 ms to feel instant (INP's good threshold); 100 ms if you want it to feel like a native control.
- Sizes: components in a view: tens to hundreds. DOM nodes: thousands (over ~1,500 Lighthouse warns). Rows in a table: hundreds visible, thousands to tens of thousands loaded. Records in memory: tens of thousands to a million for data-heavy apps. Characters in an editor: thousands to millions.
- Crossing points at 10 million ops: O(n log n) crosses around n = 500,000; O(n²) around n = 3,000; O(n³) around n = 200.
what this means
- Linear is free, once. The question for linear work is how many times per frame it runs (a linear pass per keystroke over 100k rows is fine; per mousemove is not).
- Sorting is almost free. 100k rows sort in single-digit milliseconds. Sort once per data change, not per render.
- Quadratic is the enemy, and it hides:
includesin a loop, a layout read in a loop, a keyless list, an unscoped style invalidation, string concatenation read per iteration,indexOf+splice. Chapter 2 measures four of them. - Cubic and worse are design errors that get replaced by heuristics: the O(n³) tree diff became React's O(n) reconciler by giving up on cross-level moves (part 7).
the rule
Before optimising constants, find the exponent. A 2× from micro-optimisation is a rounding error next to the 100× from removing a quadratic.
THE SIZES A UI HAS
and the complexity that fits each one
swipe the figure sideways, or tap expand for full screen
1/6
the budget
The axis: n from 10 to 1,000,000, log scale. The horizontal line is the frame budget: about 10 million simple operations in 16 ms on a mid-range device (a rough but useful constant: 1 ns per trivial op, 10 ms of budget after the browser's own work).
2
Four quadratics, measured
The same loop shape in four disguises, each timed on a 5,000-row table: a scan inside a loop. The fix in each case replaces the inner scan with something constant: a hash lookup, a single batched read, an identity, or a boundary.
code
// the most common quadratic in frontend code, and its fix
const visible = rows.filter(r => selectedIds.includes(r.id)) // O(rows × selected)
const sel = new Set(selectedIds)
const visible = rows.filter(r => sel.has(r.id)) // O(rows + selected)
// its cousins
items.find(i => i.id === id) // inside a loop over ids → build a Map once: byId.get(id)
a.filter(x => !b.includes(x)) // set difference → const B = new Set(b); a.filter(x => !B.has(x))
list.indexOf(item) === -1 // dedupe by scanning → new Set(list) or seen.has(key)
arr.splice(arr.indexOf(x), 1) // remove by value in a loop → filter once, or a Set, or swap-with-last if order is free
str += piece // in a loop, read per iteration → parts.push(piece); parts.join('') (JS course part 6)the four
includesin a filter. 5,000 rows × 2,000 selected ids = 10 million comparisons: ~12 ms. With a Set: 5,000 lookups, ~0.1 ms. The most common one, and the one most often shipped because it looks like one line.- A layout read per iteration. Setting a style then reading
offsetHeightin the same loop forces a synchronous layout per row (the browser course's part 4): 5,000 layouts, ~900 ms. Batch the writes; read once: ~3 ms. - A keyless list. Inserting one item at the top of a list rendered without keys makes the reconciler see every row as changed: 5,000 DOM updates, ~40 ms. With keys: one insert, ~0.5 ms. Part 7 is why.
- An unscoped invalidation. Toggling a class on the table re-matches selectors for all 50,000 descendants: ~30 ms. Scoping the change to the rows that change, or
contain: style, brings it to ~1 ms. Part 2 is the matching algorithm.
how to recognise the shape
- A loop over a collection, whose body calls something that walks a collection. The inner walk might be explicit (
includes,find,indexOf,filter), or implicit (a layout read, a style recalc, a reconciliation, a string flatten, aJSON.stringify, a regex over the whole text). - Time that quadruples when the data doubles. Three runs at n, 2n, 4n settle it in a minute.
- A profile with a comb (the JS course's part 14): the same narrow stack repeated thousands of times.
run it
Take the slowest list in your app. Count the rows. If any loop over them calls
includes, find, indexOf or reads layout, you have found it without a profiler.FOUR WAYS A UI GOES QUADRATIC
measured, on a 5,000-row table
swipe the figure sideways, or tap expand for full screen
1/6
includes in filter
rows.filter(r => selectedIds.includes(r.id)) with 5,000 rows and 2,000 selected ids: includes is a linear scan, inside a linear loop: 10 million comparisons, ~12 ms. Fix: const sel = new Set(selectedIds); rows.filter(r => sel.has(r.id)): 5,000 hash lookups, ~0.1 ms. 100×.
3
The toolkit: structures that turn scans into lookups
Every fix in the previous chapter was a data structure. There are about eight that matter in a UI codebase, and knowing what each makes cheap is most of algorithmic thinking at this scale.
| Structure | Fast at | Slow at | In a UI | In V8 (the JS course) |
|---|---|---|---|---|
| Array | Index O(1), push/pop O(1), ordered iteration | Search O(n), middle insert/delete O(n), shift O(n) | Lists, rows, children, buffers | Elements kinds; keep packed and typed (P3) |
| Map / Set | Lookup, insert, delete O(1); insertion order | Range queries; memory per entry | Selection, id index, memo, deps, dedupe | Ordered hash table (P12) |
| Object (as record) | Fixed-key access O(1), shape-cached | Dynamic keys (dictionary mode) | Records, props, config | Hidden classes and ICs (P3) |
| Sorted array + binary search | Search O(log n), range by two searches | Insert O(n) | Windowing by offset, timelines, breakpoints | A packed Smi/double array is ideal |
| Prefix-sum array | Range sum O(1) after O(n) build | Update O(n) (rebuild) unless a Fenwick tree | Variable-height virtualisation: offset of row k | Float64Array |
| Binary heap | Insert and pop-min O(log n), peek O(1) | Search O(n); no ordered iteration | Task schedulers, top-k, merging streams | An array; children at 2i+1, 2i+2 |
| Doubly linked list | Insert/delete at a known node O(1) | Search O(n); pointer chasing | LRU recency order; fiber tree traversal | Objects with next/prev; consistent shape |
| Tree (balanced) | Search, insert, delete O(log n); ordered | Constant factors; no built-in | Interval trees for layout queries; ordered maps | Library code; rarely needed over sorted arrays at UI sizes |
| Trie | Prefix lookup O(length) | Memory per node | Autocomplete, routers, token tables | Nested Maps or objects with consistent shape |
| Bloom filter | "Definitely not present" O(k) with no false negatives | False positives; no deletion | The CSSOM's ancestor filter (P2); large-set prefiltering | A Uint32Array of bits |
the choice
Ordered and iterated: array. Looked up by key: Map. Looked up by position in a sorted range: sorted array and binary search. Needs the smallest or the next: heap. Needs reordering on access: linked list under a Map. If none of those fits, the problem is unusual enough to deserve a library and a benchmark.
THE DATA STRUCTURE TOOLKIT
eight structures, what each makes O(1) or O(log n), and where a UI uses it
swipe the figure sideways, or tap expand for full screen
1/6
array
Array: O(1) index, O(1) push/pop at the end, O(n) search, O(n) insert or delete in the middle (elements shift). The default; the right choice for ordered data iterated in order. Under: lists, rows, children.
4
Measuring: how to know the exponent
Complexity is a claim about how time grows with size; measuring it means timing at several sizes, not one. The procedure takes a minute and settles arguments that otherwise last a sprint.
code
// measuring a suspected hot spot, in order
// 1. is it on the main thread, and how long? Performance panel → record the interaction → the Main lane
// 2. which function? Bottom-Up by self time (the top entry is the loop)
// 3. what is n? console.count / a counter in the loop body; or the data's length at the call
// 4. how does time scale with n? run at n, 2n, 4n: ×2 is linear, ×4 is quadratic. three runs settle it
// 5. is the fix a lookup, a batch, a key, or a boundary? (the four disguises; the next chapters)
// 6. measure again at the same n. and keep the measurement next to the code (a comment with the numbers)
// a scaling test, inline
for (const n of [1000, 2000, 4000]) { const d = make(n); const t = performance.now(); work(d); console.log(n, (performance.now() - t).toFixed(1)) }
// 1000: 3.1 2000: 12.4 4000: 49.8 → ×4 per doubling → quadratic. the fix is worth it.the procedure
- Find the main-thread cost with the Performance panel (the browser course, part 12): is the interaction slow because of script, layout, paint, or waiting?
- Find the function with Bottom-Up by self time (the JS course, part 14). A comb shape in the flame chart means per-item cost.
- Find n. The length of the collection the loop runs over, at the moment of the slow interaction. Log it.
- Scale it. Run at n, 2n, 4n with synthetic data. Time doubles: linear. Quadruples: quadratic. Grows by a bit more than double: n log n. The ratios are robust to noise in a way absolute numbers are not.
- Match the disguise. A scan inside the loop (lookup fix), a layout read (batch fix), position-based reconciliation (key fix), unscoped invalidation (boundary fix), or genuinely necessary pairwise work (an algorithmic change: sort first, index first, or accept and bound n).
- Measure after, at the same n, and write the before and after next to the code.
what measurement cannot replace
- Knowing n in production. Test data is small. Log the sizes from real sessions (a histogram of list lengths) before deciding whether a quadratic matters.
- Knowing the device. A mid-range phone is 4 to 6× slower than a developer laptop on single-threaded JavaScript. Throttle, or measure in the field.
- Knowing the frequency. A 5 ms linear pass is fine once per data load and a disaster per scroll event. Count the calls, not only the cost.
the pointer
Part 1 is the algorithms you write for a UI, each with its structure, its complexity, and the size at which the naive version breaks. Every one of them is a scan replaced by a lookup, a batch, or a bound.
5
The map of this course
what you write (part 1)
- Debounce and throttle as timers; virtualisation as a binary search over offsets with prefix sums for variable heights; list diffing as LCS and the keyed shortcut; LRU and LFU caches; search and ranking with inverted indexes, tries and fuzzy scores; sorting at UI scale with stable sorts and comparators that do not allocate; graph traversal for dependencies and layout; scheduling with priority queues.
what the platform runs (parts 2 to 9)
- P2 CSSOM: selector matching right to left, the ancestor bloom filter, cascade resolution as a sort, invalidation sets as set algebra.
- P3 Layout: block layout as a single pass, inline formatting and line breaking (greedy versus Knuth-Plass), the flex algorithm's passes, grid track sizing as a fixpoint, table auto layout.
- P4 Paint and compositing: paint order as a tree walk with stacking contexts, display list culling, tiling, damage rectangles.
- P5 Scheduling: the event loop's task selection, React's lane model as priority bitmasks, cooperative scheduling with deadlines, the Prioritized Task Scheduling API.
- P6 V8: hidden-class transition trees, inline cache lookup, generational collection, mark-sweep with tri-colour invariants, incremental and concurrent marking.
- P7 Reconciliation: React's heuristics, keyed reconciliation step by step, why O(n) and not O(n³), what Vue and Svelte do differently.
- P8 Compilers: tokenising as a state machine, recursive descent and Pratt parsing, SSA, constant folding, dead-code elimination, linear-scan register allocation, tree shaking as reachability.
- P9 Text: UTF-8 decoding, grapheme cluster segmentation, the bidi algorithm, hyphenation, fuzzy matching with edit distance and bitap.
how to read it
Part 1 in full; it is the part you will use this week. Parts 2 to 9 as needed, each self-contained, each pointing at the browser or JS course chapter where the same mechanism is drawn from the engine's side. This course is the algorithm; those courses are the machinery around it.