Skip to content
Algorithms Lab · LAB-10Applied Complexity

Cost Models for Interface Work

Big-O answers how cost grows, which is rarely the question a frontend engineer is actually asking. This dossier assembles the cost models that predict interface performance: per-frame budgets, allocation pressure, DOM size, and the constant factors that decide which algorithm wins at the sizes real applications use.

Level
RESEARCHER
Status
ACTIVE
Experiments
11
Observations
19

Question

Why do interfaces written with textbook-optimal algorithms still drop frames, and why does the naive implementation often win below a few hundred items?

Background

Asymptotic complexity deliberately discards constants. That is the right abstraction for comparing algorithms at unbounded size and the wrong one for a list of three hundred rows rendered sixty times a second, where the constant factor is the entire story.

ModelPredictsUnit
AsymptoticScaling behaviouroperations as n grows
Frame budgetWhether a frame shipsmilliseconds out of 16.7
AllocationCollector pressure and jankobjects surviving a scavenge
DOM sizeStyle, layout and memory costnodes and depth
Four cost models, and what each one predicts

Findings

Finding 1. The crossover point is usually higher than expected. Linear scans over small contiguous arrays are extremely cache friendly. A Map wins decisively at scale and can lose at a handful of items, so the honest answer to which is faster is a measurement, not a table.

Finding 2. Quadratic work hides inside linear-looking code. A lookup inside a render, a filter inside a map, a deduplication that compares every pair: each reads as one loop and behaves as two.

Finding 3. The DOM has its own exponent. Rendering n rows costs style resolution, layout and memory per node regardless of how efficiently the data was prepared. Virtualisation changes that term; a better algorithm does not.

Finding 4. Frame budget is a hard constraint, not an average. A 12ms mean with a 40ms tail produces visible stutter. Interface performance is governed by the worst frames, which makes percentiles the only honest summary.

Method

  1. 01Measure at the sizes your application actually reaches, not at the size that makes the graph dramatic.
  2. 02Throttle the CPU. An algorithm that fits the budget on a workstation may not on a mid-range phone.
  3. 03Separate build cost from query cost. Indexing once and reading many times is a different profile from doing both in a loop.
  4. 04Record the distribution, not the mean, and treat the long tail as the result.

Limitations

References

  1. 01web.devOptimize long tasks
  2. 02web.devRendering performance
  3. 03V8 blogTrash talk, the Orinoco garbage collector