Algorithmic Cost in a Request Handler
An O(n²) loop over a collection that grew is a CPU bottleneck that scales with data, not traffic — which is why it passes load tests and fails in production. And the counterpoint: Big-O does not price cache locality, branch prediction or constants.
Frame the diagnosis
Performance work starts from a symptom and a signal — never from a resource dashboard.
The cost that scales with data, not traffic
The classic shape: a handler that looks fine in review, in tests and in staging, because everywhere except production the collection has twelve elements. At 12 items an O(n²) pass is 144 operations and invisible. At 4,000 items it is 16 million, and one endpoint owns a core for two seconds. Nothing changed in the code; the customer grew.
This is why traffic-shaped load tests miss it. Ramping RPS with a fixed synthetic payload multiplies a cheap operation; it never produces the one request with a large n. The test that would have caught it varies *data size*, not request rate — which is the workload-modelling point in Load Testing: What Question Is This Test Answering?, and the reason Benchmark Fallacies: Confident Numbers That Are Wrong lists unrealistic payloads as a top offender.
The tell in telemetry is a correlation you have to deliberately record: latency against a size attribute on the span (items.count, result.rows). Without that attribute, the endpoint just has a mysteriously bimodal distribution and everyone blames the database. With it, the scatter is unmistakable — and a plot that curves upward rather than rising linearly names the complexity class directly.
1// "find duplicates across the submitted lines"2for (const line of lines) {3 for (const other of lines) {4 if (line.id !== other.id && line.sku === other.sku) {5 conflicts.push([line, other])6 }7 }8}9// n=12 → 144 comparisons (0.1 ms)10// n=400 → 160,000 comparisons (~14 ms)11// n=4,000 → 16,000,000 comparisons (~1.4 s, one core)12//13// Load test at 10x RPS with n=12 payloads: still 0.1 ms. Ships green.1if (lines.length > MAX_LINES) throw badRequest('TOO_MANY_LINES')2 3const bySku = new Map<string, Line[]>()4for (const line of lines) {5 const group = bySku.get(line.sku) ?? []6 group.push(line)7 bySku.set(line.sku, group)8}9for (const group of bySku.values()) {10 if (group.length > 1) conflicts.push(group)11}12// n=4,000 → ~4,000 inserts + one pass (~2 ms)13//14// span.setAttribute('lines.count', lines.length) ← makes the next one visibleTwo changes, and the second matters as much as the first. The hash map removes the quadratic term; the explicit bound turns an unbounded input into a documented contract limit (Large Requests and Documented Limits), so a future pathological payload gets a 400 instead of a core. The span attribute is what makes the *next* size-driven regression a five-minute diagnosis instead of a week.
Where Big-O stops predicting
The honest counterpoint, and the one that separates people who have optimized real code from people who have only analyzed it: complexity classes describe growth, not cost. They deliberately discard the constant factor, and on modern hardware the constant factor is where a 10× difference lives. A linear scan over a contiguous array frequently beats a "better" pointer-chasing structure at realistic sizes, because the array walks sequential cache lines with a prefetcher that predicts every step, while the tree takes a cache miss per level — and a last-level cache miss is worth roughly a hundred arithmetic operations, ENVIRONMENT-SPECIFIC but not by a little.
Branch prediction is the second thing Big-O cannot see. A tight loop with a predictable branch runs near peak throughput; the same loop with an unpredictable, data-dependent branch stalls the pipeline on every misprediction. This is why sorting the input before scanning it can make the *scan* faster — the branch becomes predictable — even though sorting is strictly extra work.
The practical rule: use complexity to rule out disasters (never ship an accidental O(n²) over unbounded user input), then use a profile and a benchmark to choose among the survivors (Measure Before You Optimize, Microbenchmark or End-to-End: Why p99 Did Not Move). "Asymptotically better" is a hypothesis about large n; the profile is evidence about your n. If your n is 200 and will always be 200, the simpler structure usually wins on both speed and maintenance.
| Factor | Visible in Big-O? | Why it changes the real answer |
|---|---|---|
| Growth with n | Yes — this is the whole point | Rules out designs that fall off a cliff as data grows. Use it here. |
| Constant factor | No, discarded by definition | A 50× constant makes an O(n log n) structure lose to an O(n²) scan until n is large. |
| Cache locality | No | Contiguous access is prefetched; pointer chasing takes a miss per hop. Often the dominant term at realistic n. |
| Branch prediction | No | Data-dependent branches stall the pipeline; predictable ones are nearly free. |
| Allocation cost | No | A structure that allocates per element adds GC pressure invisible to the complexity class (Allocation Rate Is a Cost Even Without a Leak). |
| The actual n in production | No — it is asymptotic | The only question that matters operationally, and the only one your telemetry can answer. |
Finding it: the size attribute is the whole trick
Algorithmic cost is one of the few performance problems where a single instrumentation decision converts a hard diagnosis into a trivial one. Record the size parameter as a span attribute on every request: number of items submitted, rows returned, elements in the collection being processed. Then latency-versus-size is a scatter plot instead of a mystery, and the curve's shape names the complexity class.
The CPU profile confirms it and localizes it: a size-driven quadratic shows up as one very wide frame that grows wider as you sample the slow requests specifically (Reading a Flame Graph). Profiles aggregated across all requests dilute it — 95% of requests are cheap — so profile the slow population if your tooling can filter, or correlate profile samples with the slow trace window.
Note what this is *not*. If latency correlates with RPS rather than with size, you have ordinary capacity saturation (CPU Saturation: When Cores Become the Queue), and the fix is capacity or per-request cost across the board. If latency correlates with size but on-CPU time is low, the cost is not algorithmic at all — you are probably making one call per element to a database or a service, which is The Comb: N+1 as a Visible Shape and needs batching, not a better data structure.
| Signal | Value | What it tells you | Verdict |
|---|---|---|---|
| Latency vs RPS correlation | r ≈ 0.1 | Traffic is not the driver. Rules out ordinary capacity saturation. | normal |
| Latency vs `lines.count` correlation | r ≈ 0.94, curve superlinear | Cost tracks data size and grows faster than linearly. Algorithmic. | smoking gun |
| On-CPU / wall-clock ratio (slow requests) | 0.96 | The time is spent computing, not waiting. Confirms CPU-bound work. | smoking gun |
| DB spans per request (slow requests) | 3 | Not a per-element query fan-out — rules out N+1. | normal |
| p50 latency | 48 ms (unchanged for months) | Most requests are small, so aggregate dashboards look healthy throughout. | normal |
| p99.9 latency | 2.4 s | The largest accounts live entirely in the extreme tail. | smoking gun |
Key points
- Algorithmic cost scales with data size, not request rate — which is exactly why RPS-shaped load tests ship it to production.
- Record a size attribute on the span; latency-versus-size turns an unexplained bimodal distribution into a named complexity class.
- Big-O rules out disasters. It does not price constant factors, cache locality, branch prediction or allocation, and those dominate at realistic n.
- Confirm CPU-bound before rewriting: if on-CPU time is low but latency tracks size, it is a per-element I/O fan-out, not an algorithm.
- Bounding the input is half the fix — an unbounded n in a handler is a contract problem as much as a performance one.
Follow the diagnosis
The causal chain, hop by hop — and the readings that invite the wrong conclusion.
- 1Customer data → request payload: an account that grew now submits 4,000 line items where the design assumed dozens.
- 2Payload → handler loop: the nested pass performs n² comparisons, all on-CPU, all inside one request.
- 3Handler → core occupancy: one request holds a core for seconds, so concurrent requests queue behind it (Queueing: Why Systems Get Slow Before They Get Broken).
- 4Core occupancy → tail latency: the affected accounts see multi-second responses while the median is untouched.
- 5Aggregate dashboards → operator: p50 and utilization look normal because large accounts are a tiny fraction of traffic, so nobody investigates until a customer escalates.
- • "It is slow for that customer because they have more data, that is expected" — linear growth is expected; superlinear growth is a defect.
- • "The load test passed, so throughput is fine" — the load test used a fixed small payload and measured a different code path in practice.
- • "The database must be slow for big accounts" — check span counts and on-CPU time before blaming storage; the CPU may never have left the handler.
- • "Big-O says this structure is better, so this is the fix" — verify with a benchmark at your real n; asymptotics routinely lose to constants below a million elements.
- • "p99 is within SLO" — with a long-tailed size distribution, the harmed users can sit entirely beyond p99.
Measure, fix, validate
An optimization is not finished until the metric that motivated it has moved.
- • A size attribute on every relevant span (`items.count`, `rows.returned`), then latency plotted against it.
- • Correlation of latency with size versus latency with RPS — the two have completely different fixes.
- • On-CPU time versus wall-clock time for the slow request population specifically, not the aggregate.
- • A CPU profile filtered to slow requests; the quadratic frame widens as n grows.
- • p99.9 as well as p99 — with a small population of large accounts, p99 can still look acceptable.
- • Remove the superlinear term with an appropriate data structure — usually a hash map for membership or grouping ([[hash-map]]), sorting plus a linear pass for ordering-dependent work.
- • Bound the input explicitly and return a clear error above the limit, so an unbounded n is impossible by contract ([[large-requests]]).
- • Move genuinely large-n work out of the request path into a job the client polls ([[async-job-pattern]]).
- • Add the size attribute permanently — the instrumentation is the durable fix; the algorithm is one instance.
- • Only then micro-optimize, and only against a benchmark at production-realistic n ([[microbenchmark-vs-system]]).
- • Re-run against the largest real payload you can obtain and compare wall-clock time at that specific n, not at the average n.
- • Confirm the latency-versus-size curve is now linear (or flat) across the observed range, not just lower at one point.
- • Check that p99.9 for the affected account cohort moved, since that is where the harm was concentrated.
- • Confirm no new allocation or GC cost was introduced by the replacement structure ([[allocation-profiling]]).
- • Hash-based structures trade memory and allocation for time; on very small n the extra allocation can be slower than the naive loop.
- • Input bounds are a breaking change for any client that was legitimately sending more, so they need a migration path.
- • Moving work to an async job removes the latency problem but adds a job resource, polling and a more complex client contract.
- • A benchmark in CI at a realistic large n with a wall-clock threshold — the smallest guard that would have caught the original (Regression or Tuesday? Telling a Real Change from Noise).
- • A hard input bound enforced at the API boundary, documented as part of the contract.
- • An alert on latency-versus-size drift, or at minimum p99.9 by endpoint, so tail-only regressions surface.
- • Load-test scenarios that vary payload size, not only request rate (Load Test Shapes: The Shape Is the Hypothesis).
Accuracy
Performance numbers are conditional. These are the conditions.
- ILLUSTRATIVEThe operation counts, timings and correlation coefficients are invented to show the shape. Actual per-operation cost depends on language, data layout and hardware.
- WORKLOAD-SPECIFICWhether a quadratic pass matters depends entirely on the distribution of n in your production traffic, which is why the size attribute matters more than the complexity analysis.
- ENVIRONMENT-SPECIFICThe cache-miss-versus-arithmetic ratio, and therefore when a "worse" flat structure beats a "better" pointer-based one, varies by CPU generation, cache size and memory layout.
Misconceptions
Apply it
Where the depth lives
DSA teaches how to derive the growth class. This lesson is about when that class predicts production behavior and when constants, caches and the actual distribution of n overrule it.
The reason a "worse" contiguous scan beats a "better" tree at realistic sizes is not taught by complexity analysis at all — it is prefetching and pipeline behavior, and it is where the constant factor lives.