skip to content

Which shape in a regular-expression search makes its cost grow quadratically with input length rather than exponentially?

level: middleimportance: nice to knowfreq 27%

answer

  1. two loops, not one
  2. restarting at every starting offset
  3. no anchor, leading quantifier
  4. n times n over two
  5. caps work on polynomial cost

basics

~20 s

An unanchored search whose pattern starts with a quantifier: the matcher retries the whole attempt at every starting offset, and each attempt can scan most of the input. That gives about n(n+1)/2 steps, quadratic rather than exponential.

solid answer

~40 s

Quadratic cost comes from the **outer** loop, not from ambiguity inside the pattern. When a pattern is not anchored, a matcher that fails at offset 0 restarts the entire attempt at offset 1, then 2, and so on. If each attempt walks a long run before failing — for example `[a-z]+!` against a field of letters with no `!` anywhere — the total is n + (n-1) + ... + 1, which is n(n+1)/2. There is no branching and no doubling, so it is far milder than a nested quantifier: doubling the input quadruples the time instead of squaring it. It still matters, because on a 100,000-symbol field that is roughly 5e9 symbol comparisons, seconds of pinned processor per request.

code

pseudocode · 9 lines
pseudocode
# unanchored search: the whole attempt restarts at each offset
for start from 0 to length(text) - 1:
    if attempt_match(text, start):     # walks up to length(text) - start symbols
        return match found at start

return no match

# worst case, when every attempt walks to the end and then fails:
#   n + (n - 1) + ... + 1  =  n * (n + 1) / 2

go deeper

for a junior

Know that there are two different slow shapes, and that a pattern searching an unanchored field can quietly do work proportional to the square of the field length.

for a middle

Explain the restart loop: each failed attempt costs a scan, and there is one attempt per starting offset, summing to n(n+1)/2. Then say why anchoring removes that factor.

for a senior

Recognise the signature in production data — time that quadruples when the field doubles — and pick the matching fix rather than applying the exponential-case fix by reflex.

for a principal

Decide where field-length limits are set and enforced across services, knowing that a cap is a real control against polynomial cost and close to worthless against exponential cost.

## Where the second factor comes from Two different loops can make a pattern expensive, and confusing them leads to the wrong fix. - **The inner search** over the ways a pattern can match at one starting position. Ambiguity lives here, and it is what produces exponential cost. - **The outer restart loop** over starting positions. A search that is not anchored asks 'does the pattern match starting here?' at offset 0, then offset 1, and so on until it succeeds or runs out of input. Quadratic cost is the second loop alone. Nothing inside the pattern is ambiguous; the attempt at each offset is perfectly deterministic. It is simply performed up to n times, and each attempt can walk most of the remaining input before failing. The classic shape is a pattern that begins with a quantifier over a common class and then demands something the input never provides: `[a-z]+!` over a field of 100,000 letters with no `!` in it. At offset 0 the matcher consumes all 100,000 letters, looks for `!`, and fails. It then starts at offset 1 and consumes 99,999. The sum n + (n-1) + ... + 1 is n(n+1)/2, about 5e9 comparisons at n = 100,000 — enough to pin a worker for seconds on every such request. ## Exponential against quadratic, side by side | | Quadratic | Exponential | |---|---|---| | Source | restarting an unanchored search at each offset | many match paths at one offset | | Pattern smell | leading quantifier, no anchor, required tail | quantifier under a quantifier, overlapping branches | | Doubling the input | about four times the work | squares the work | | Effect of a length cap | effective: cap of 1,000 caps cost at about 5e5 steps | weak: even a small cap leaves a huge number of paths | | Symptom | steady processor burn, latency that scales with field size | one request that never finishes | The row that matters operationally is the length cap. Because quadratic cost is polynomial, halving the maximum field length quarters the worst case, so a cap is a genuine control. Against doubling-per-symbol growth a cap is almost useless: cutting a 200-symbol limit to 100 still leaves 2^99 paths, a number with no operational meaning. ## Why quadratic still ends in an incident It is tempting to file this as 'merely slow'. Three reasons not to: - **It scales with an attacker-controlled dimension.** The cost is a function of a field the caller chooses. - **It multiplies by concurrency.** A single request burning two seconds of processor is survivable; a hundred concurrent ones saturate every core, and other endpoints degrade with it. - **It hides.** Exponential cost announces itself as a request that never returns. Quadratic cost looks like a slow endpoint, gets attributed to the datastore or the network, and can live in a system for a long time. ## Fixes that actually apply here 1. **Anchor the search** if the pattern is meant to describe the whole field. Anchoring at the start removes the restart loop entirely, which removes the factor of n — an anchored deterministic pattern is linear. 2. **Cap the field length** at the smallest value the domain genuinely needs, and do the cap **before** matching rather than after. 3. **Cheap pre-check first.** If a match requires a rare literal, test for that literal with a plain substring scan before invoking the matcher at all; the failing case then costs one linear pass. 4. **Do not confuse this fix with the other one.** Anchoring does nothing for a quantifier nested in a quantifier, and rewriting an ambiguous group does nothing for an unanchored scan. Diagnose which loop you are in by asking whether the pattern is ambiguous at a single fixed offset. ## Reading the signature in production Plot request time against the length of the suspect field. Linear growth is healthy. A curve that quadruples when the field doubles is the restart loop. A curve that explodes between two nearby lengths — fine at 30 symbols, unfinished at 45 — is ambiguity inside the pattern, and anchoring will not save you.

  • Why does a length cap control quadratic cost but barely help against exponential cost?
    Because the two grow differently in the cap. Quadratic cost is proportional to the square of the limit, so halving the limit quarters the worst case — a real, predictable control. Exponential cost doubles per symbol, so cutting a limit from 200 to 100 still leaves 2^99 paths. A cap is a legitimate guard for the first and a fig leaf for the second.
  • How do you tell the two failure modes apart from outside the process?
    Measure time against field length at several sizes. Quadratic growth quadruples the time when the length doubles and stays smooth. Exponential growth is flat and then falls off a cliff between two nearby lengths — comfortable at 30 symbols, unfinished at 45. The curve tells you whether to anchor the search or to rewrite the pattern.

saying these in an interview costs you the question

  • Calls quadratic backtracking harmless because it finishes
  • Anchors a pattern and declares nested quantifiers fixed
  • Thinks only exponential patterns can cause an incident
  • Confuses restarting at each offset with ambiguity inside the pattern
  • Applies an input cap and assumes any pattern is now safe