DEV Community: Arpan Singh

Big-O Notation Explained: The Regex That Took Down Cloudflare for 27 Minutes

Arpan Singh — Fri, 24 Jul 2026 12:09:43 +0000

At 13:42 UTC on July 2, 2019, Cloudflare's network stopped answering requests. Not slow. Down.

For 27 minutes, a huge slice of the web returned 502 errors instead of loading.

The cause wasn't a DDoS attack or a hardware failure. It was one regular expression, in one firewall rule, pushed to every server Cloudflare owns at the same time.

That regex had a property called catastrophic backtracking. Feed it the wrong kind of input, and instead of matching in microseconds, the matching time roughly doubles with every extra character.

Cloudflare's own post-mortem lays it out plainly: a WAF rule update shipped a regex that ate CPU on every core handling HTTP and HTTPS traffic, worldwide, within minutes of going live.

That single deployment is the entire reason Big-O notation is worth learning as a working developer, not just memorizing for an interview and forgetting.

Every data structure and algorithm in this series has a Big-O. Get it wrong, and code that sails through testing can take your production system down exactly like it did for Cloudflare.

What Big-O Actually Measures

Big-O is not a stopwatch. It doesn't tell you an operation takes "3 milliseconds."

It tells you how the cost of an operation grows as the input grows. That's the whole idea.

Say a function checks every item in a list once. Double the list, and the function does roughly double the work. That growth pattern, cost scaling linearly with size, is what O(n) describes.

Big-O deliberately throws away two things: the exact hardware you're running on, and small, constant-size costs. It keeps only the part that matters once your input gets big: the shape of the growth curve.

That's also why the Cloudflare regex was so dangerous. Its growth curve wasn't linear, or even quadratic. It was exponential, and exponential curves look almost flat for small inputs, then explode the moment the input crosses a threshold. That's exactly the kind of bug that passes every test and detonates in production.

Dropping Constants: Reading Big-O Like an Algebra Problem

Say you profile a function and its operation count comes out to:

3n² + 5n + 2

Big-O notation calls this function O(n²). Here's why, term by term.

Drop the lower-order terms. Once n gets large, 5n and 2 stop mattering next to 3n². At n = 1,000,000: 3n² is 3 trillion, 5n is 5 million. A rounding error by comparison.

Drop the constant multiplier. Whether it's 3n² or 30n², both describe the same shape of growth: quadratic. The multiplier affects real-world speed, which is a separate conversation from Big-O, but it doesn't change the growth curve.

So 3n² + 5n + 2 becomes O(n²), every time. This is the most common thing beginners get wrong — they see two nested loops and one extra pass, and try to write O(2n² + n). Nobody writes that. It's O(n²).

The Complexity Ladder

Here's every complexity class you'll run into in this series, best to worst, each with one operation you already use.

	Notation	Name	A real example
🟢	O(1)	Constant	Reading arr[5] from an array
🟢	O(log n)	Logarithmic	Binary search on a sorted array
🟢	O(n)	Linear	Scanning a list once for a value
🟡	O(n log n)	Log-linear	Sorting with merge sort or Python's Timsort
🟠	O(n²)	Quadratic	Comparing every pair with nested loops
🔴	O(2ⁿ)	Exponential	Naive recursive Fibonacci — and Cloudflare's regex
🔴	O(n!)	Factorial	Trying every ordering of n items

Green means it scales to millions of items without blinking. Yellow still holds up at real-world scale. Orange starts hurting once n hits the thousands. Red is the zone Cloudflare's regex lived in — fine for tiny inputs, catastrophic past a threshold.

Each step down that table is a different universe of slowdown. At n = 20, O(n) and O(2ⁿ) are both fast. At n = 40, O(n) is still instant. O(2ⁿ) has over a trillion steps left to run.

Best Case, Average Case, Worst Case

Big-O by itself usually means the worst case: the input that makes an algorithm work hardest.

Linear search through an unsorted list is O(n) worst case (the value isn't there, or it's last) but O(1) best case (it's the first element checked).

Quicksort is the classic split-personality algorithm: O(n log n) on average, but O(n²) worst case if it keeps picking a bad pivot on already-sorted data. That's exactly why production sort implementations (Python's Timsort, V8's sort) don't run plain quicksort. They hedge against that worst case directly.

When someone asks "what's the Big-O of this," they almost always mean the worst case unless they say otherwise. That's the convention this series follows too.

Space Complexity: The Other Half of the Bill

Big-O also measures memory, not just time. Same rules, different resource.

An algorithm that builds a second array the same size as the input is O(n) space. One that tracks a couple of variables, regardless of input size, is O(1) space.

Recursive functions carry a space cost most beginners miss: every call sits on the call stack until it returns. A recursive function that goes n levels deep uses O(n) space on the stack alone, even without allocating a single array. That'll matter once recursion shows up properly in Day 3.

Amortized Time: Why "Append" Isn't Always O(1)

Both Python's list.append() and JavaScript's array.push() get described as O(1). That's not the whole story.

Under the hood, both languages back their dynamic arrays with a fixed-size block of memory. Fill it up, and the next append has to allocate a bigger block and copy every existing element over — an O(n) operation.

Both languages soften this the same way: they over-allocate, growing the backing array by a multiplying factor instead of one slot at a time. Resizes get rarer as the array grows, so the average cost per append, across many appends, still comes out to O(1). That average has a name: amortized O(1). It's worth knowing before dynamic arrays show up properly in Day 2.

How to Read Your Own Code's Complexity

There's a repeatable process here, simpler than it looks once you've done it a few times.

flowchart TD
    A[Look at the loops] --> B{Loops nested?}
    B -->|No, sequential| C["Add them: O(a) + O(b), keep the larger term"]
    B -->|Yes| D["Multiply them: O(a) times O(b)"]
    D --> E{Does each step cut<br/>the input in half?}
    E -->|Yes| F["O(log n) for that part"]
    E -->|No| G["O(n) for that part"]
    C --> H{Any recursive calls?}
    G --> H
    F --> H
    H -->|Yes| I["Count total calls made,<br/>not just the visible loop"]
    H -->|No| J["Done, that's your Big-O"]

Walk that against a real function:

def has_duplicate_pair(nums):
    for i in range(len(nums)):             # loop 1: n iterations
        for j in range(i + 1, len(nums)):  # loop 2: nested inside loop 1
            if nums[i] == nums[j]:
                return True
    return False

Two loops, nested. That means multiply. Loop 1 runs n times, loop 2 runs roughly n times too (shrinking a bit each pass, a detail Big-O ignores). O(n) times O(n) = O(n²).

Compare that to a function that looks similar but isn't:

def has_negative_or_over_limit(nums, limit):
    for n in nums:               # loop 1: n iterations
        if n < 0:
            return True
    for n in nums:                # loop 2: separate, not nested
        if n > limit:
            return True
    return False

Two loops again, but sequential, not nested. Add instead of multiply: O(n) + O(n), the constant drops, and it's O(n). Seeing "two loops" and assuming O(n²) automatically is one of the most common mistakes in code review.

The Benchmarks: What This Looks Like on Real Hardware

Theory is one thing. Here's what these growth curves look like measured for real — Python 3.12 and Node.js 22, same machine, same inputs, timed with timeit and process.hrtime.bigint().

O(1): array index access

n	Python (ns/op)	Node.js (ns/op)
1,000	43.3	14.2
10,000	31.3	9.5
100,000	32.1	10.4
1,000,000	30.8	27.2

Flat, as expected. The time doesn't track n at all. The small jump at 1,000,000 in the Node.js column isn't a Big-O violation; that's the array outgrowing CPU cache, a real hardware effect Big-O doesn't model. Big-O describes algorithmic growth, not what the cache hierarchy underneath it is doing.

O(log n): binary search

n	Python bisect (ns/op)	Node.js (ns/op)
1,000	114.8	35.8
10,000	121.7	24.9
100,000	156.8	25.4
1,000,000	159.0	28.6

The input grew 1,000x. The time barely moved. That's the entire pitch for logarithmic algorithms in one table.

O(n): linear search, worst case (target never present)

n	Python (µs/op)	Node.js (µs/op)
1,000	6.62	1.11
10,000	59.49	10.14
100,000	616.47	102.58
1,000,000	6,060.19	1,514.06

10x the input, roughly 10x the time, in both languages. Textbook linear.

O(n log n): sorting (Python's Timsort, V8's sort)

n	Python (ms/op)	Node.js (ms/op)
1,000	0.083	0.202
10,000	1.262	2.057
100,000	18.386	26.654
1,000,000	260.294	326.918

Growing faster than linear, much slower than quadratic — the middle ground n log n describes. Don't read too much into Python edging out Node.js here; it's one machine, one run, and the gap is small enough that engine warm-up explains most of it, not "Python's sort is better."

O(n²): checking every pair for duplicates, nested loops

n	Python (ms/op)	Node.js (ms/op)
500	3.25	0.09
1,000	13.82	0.34
2,000	53.97	1.32
4,000	219.10	5.29

Double n, and the time roughly quadruples, in both languages, at every step. That's the signature of O(n²): a pattern you can watch happen in real numbers.

O(2ⁿ) vs O(n): naive vs. memoized Fibonacci

n	Naive Python (ms)	Memoized Python (µs)	Naive Node.js (ms)	Memoized Node.js (µs)
20	0.663	7.63	0.091	3.61
25	8.613	6.01	0.706	4.31
30	78.953	6.84	7.700	5.18
32	206.629	7.15	20.428	5.11

This is the table that matters most in the whole post. Going from n=30 to n=32 — adding two — makes the naive version take roughly 2.6x longer, in both languages independently. That 2.6x isn't a coincidence: it's the golden ratio squared, baked into how Fibonacci's recursion tree branches.

The memoized version barely moves across the entire range. One dictionary, or one Map, turns an O(2ⁿ) function into an O(n) function. The benchmark shows exactly what that's worth: milliseconds versus microseconds.

The benchmark scripts used to generate the numbers listed above have been uploaded to GitHub for reference.

def fib_naive(n):
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)

def fib_memo(n, cache={}):
    if n <= 1:
        return n
    if n in cache:
        return cache[n]
    cache[n] = fib_memo(n - 1, cache) + fib_memo(n - 2, cache)
    return cache[n]

Where the Regex Went Wrong

Back to Cloudflare, with the vocabulary to actually explain it now.

A backtracking regex engine, faced with an ambiguous pattern, can end up trying every possible way to match it — the regex equivalent of the naive Fibonacci function above, except n is the length of the input string, and there's no memoization built in by default.

Small inputs, like most real traffic, never trigger the worst case. That's exactly why the rule passed testing.

One request with the right shape of pathological input turned a normally instant regex into an O(2ⁿ) computation, run on every CPU core, on every server, at the same time. That's the outage in one sentence.

What's Next

Day 2 starts with arrays. There's enough ground there to split it: fundamentals and core operations first, then patterns like two-pointer and sliding window as their own follow-up. Linked lists get the same treatment once we reach them: singly and doubly linked first, then the interview-heavy patterns (reversal, cycle detection, merging) as a separate post.

Every post from here on states the time and space complexity of every operation it covers. This is the post that vocabulary comes from.

Originally published on ZyVOP

💡 For more articles like this, subscribe to the ZyVOP newsletter!

Arrays Explained from Memory to Big O (With Real Benchmarks)

Arpan Singh — Fri, 24 Jul 2026 12:08:55 +0000

This Loop Should Delete Three Items. It Deletes Two.

scores = [45, 30, 88, 92, 15, 67]

for score in scores:
    if score < 50:
        scores.remove(score)

print(scores)

Read that and guess the output. Three values are under 50: 45, 30, 15. So the obvious guess is [88, 92, 67].

Run it, and Python prints [30, 88, 92, 67].

30 survives. Nothing crashed, no exception, no warning. The code just quietly kept a value it was explicitly told to remove.

Swap the language and the bug follows you:

const scores = [45, 30, 88, 92, 15, 67];

for (let i = 0; i < scores.length; i++) {
  if (scores[i] < 50) {
    scores.splice(i, 1);
  }
}

console.log(scores);

Same input, same wrong survivor: [ 30, 88, 92, 67 ].

Two different languages, two different removal methods, the exact same failure. That's not a coincidence. It's what an array is underneath both of them, and Day 2 starts there.

What An Array Actually Is

Forget the syntax for a second. At the hardware level, an array is a promise: a single, unbroken block of memory, where every element sits the same distance apart.

That promise is what makes scores[3] fast. The computer doesn't search for index 3. It calculates an address directly: start of the block, plus 3 times the size of one element, done. One arithmetic operation, one memory read. That's the entire reason array access is O(1): it's not clever, it's just math.

Deletion breaks that promise, at least temporarily. Remove the item at index 0, and there's now a gap at the front of an otherwise unbroken block. The only way to restore the promise (a single contiguous run with no holes) is to physically slide every element after the gap back by one position.

That slide is the whole story. It's an O(n) memory move hiding behind a one-line method call, and it's exactly what desynced the loop above.

Why The Loop Skips

Walk scores.remove(score) through what actually happens in memory, one step at a time:

The loop's cursor sits at index 0. It reads 45, sees it's under 50, and removes it.
Removing index 0 slides everything left by one slot. The value that used to be at index 1, 30, is now sitting at index 0.
The loop cursor doesn't know that happened. It advances to index 1, as it always does.
Index 1 now holds 88, the value that used to be two slots over. 30 was never re-examined. It's still in the array when the loop ends, because the loop moved past the exact slot it landed in.

The fix follows directly from the same mental model. Either walk the array backward, so every shift happens behind the cursor instead of into it:

scores = [45, 30, 88, 92, 15, 67]

for i in range(len(scores) - 1, -1, -1):
    if scores[i] < 50:
        scores.pop(i)

or don't mutate the array you're iterating at all, build a new one instead:

scores = [45, 30, 88, 92, 15, 67]
scores = [s for s in scores if s >= 50]

The second version is also the one worth defaulting to. It sidesteps the shifting problem entirely instead of just working around it.

Static Arrays vs. What You're Actually Using

C's int arr[10] is a static array: one fixed-size block, allocated once, that can never grow. Ask for an 11th slot and there's no polite failure. You're writing into memory that belongs to something else.

Python's list and JavaScript's Array aren't that. They're dynamic arrays: a static array under the hood, wrapped in logic that swaps in a bigger block once the old one fills up. Every .append() or .push() you've ever called was secretly asking "is there room?" before it ever touched memory.

That wrapping is why beginners get told arrays are O(1) to append to, and it's mostly true, but "mostly" is doing real work in that sentence, covered next.

Every Core Operation, Rated

	Operation	Complexity	Why
🟢	Access by index	O(1)	Direct address math, no searching
🟢	Append / pop at the end	O(1)*	No shift needed; *occasionally O(n) — grows past capacity, shrinks past half capacity, more below
🟠	Search (unsorted)	O(n)	No shortcuts — check every slot until found
🔴	Insert / delete at the start	O(n)	Every remaining element shifts by one
🔴	Insert / delete in the middle	O(n)	Same shift, just for a shorter stretch

The pattern in that table is the entire lesson: where in the array you operate matters as much as what operation you run. The end is cheap. The front is expensive. That's not a Python or JavaScript quirk. It's physics, the same physics that broke the loop above.

The Asterisk on "O(1) Append"

Dynamic arrays grow by over-allocating: when the backing block fills up, they don't grab one more slot, they grab a noticeably bigger block and copy everything over. That copy is O(n), but it happens rarely enough that the average cost per append, over many appends, still comes out to O(1). That average has a name: amortized O(1).

"Rarely enough" isn't hand-waving. CPython's growth pattern is public, and it's checkable from Python itself, since sys.getsizeof() reports the backing array's real allocated size, not just the list's length. Appending one item at a time and watching that number jump gives you the exact resize points, live, on CPython 3.12:

List length at resize	Backing array size (bytes)	Slots allocated
1	88	4
5	120	8
9	184	16
17	248	24
25	312	32
33	376	40

Between each row, appends are just writing into already-reserved space: genuinely O(1), no copying at all. The resize itself, on that one unlucky append, is O(n). Spread that occasional O(n) cost across all the free appends in between, and it averages out to O(1) per call.

Shrinking runs the same machinery in reverse, on a different trigger than most people guess. pop() doesn't hand memory back the moment the list gets smaller: CPython only reallocates down once the length falls under half of what's currently allocated, not the instant a single slot goes unused. Pop a 33-item list down to empty and the real shrink points, traced the same way with sys.getsizeof(), land at lengths 16, 11, 7, 5, 1, and 0. Compare that to the growth table above and the thresholds don't mirror each other; growing and shrinking are governed by two separate rules sharing one function, not a single reversible curve.

V8 runs the same strategy for JavaScript arrays, over-allocating on growth instead of resizing one slot at a time. That's why .push() gets the same amortized O(1) label .append() does.

One More Thing V8 Tracks That CPython Doesn't

V8 keeps something called an array's elements kind — a running classification of what's actually in it: all small integers, mixed with floats, holding arbitrary objects, or containing gaps. V8's own engineering blog lays out the mechanism: arrays built with actual gaps in them (skipped indices, or presized with new Array(n) and filled out of order) get marked holey, and every read from a holey array carries an extra check a gap-free ("packed") array skips.

That transition only runs one direction: specific to general, packed to holey. It's permanent. Fill every gap in a holey array later, and V8 still won't reclassify it back to packed. The practical takeaway: build arrays in order, front to back, if you want V8 to keep every optimization available to it.

How much that actually costs in practice is genuinely inconsistent. A plain summation loop over a packed vs. a holey million-element array, benchmarked repeatedly on this machine, came back centered close to even, drifting up to roughly 13% either direction depending on the run, with no consistent winner. Real, but not the dramatic one-directional gap sometimes claimed for it online. The scripts to run that comparison yourself are in the attached zip.

The Benchmarks

Same rule as Day 1: no number below is estimated. Python 3.12 and Node.js 22, timed with time.perf_counter() and process.hrtime.bigint(), each operation paired with its opposite (append then pop, insert then remove) so the array's size stays constant across the whole run.

End of the array: append / pop

n	Python append (ns)	Python pop (ns)	Node push+pop (ns, combined)
1,000	44.9	31.0	10.0
10,000	31.4	31.0	1.9
100,000	32.1	30.9	2.0
1,000,000	31.7	34.6	1.7

Flat across four orders of magnitude, in both languages. That's the empirical signature of O(1). The Node numbers look almost too fast to be real; that's V8's JIT compiling this exact push-then-pop pattern more aggressively the longer the process runs, not a language-superiority result. Treat the flatness as the finding, not the specific nanosecond count.

Start of the array: insert / delete

n	Python insert(0) (µs)	Python pop(0) (µs)	Node unshift (µs)	Node shift (µs)
1,000	0.26	0.12	0.14	0.12
10,000	2.60	1.84	1.85	0.13
100,000	24.77	17.97	18.65	18.39
1,000,000	364.64	342.58	362.43	348.51

10x the input keeps landing close to 10x the time, in every column. That's the same linear signature the O(n) search benchmark showed on Day 1, now showing up for a different operation entirely. (Node's shift at n=10,000 reads oddly low next to its neighbors — at that size the fixed cost of the function call itself is still competing with the shift cost, so the line hasn't straightened out yet. It does by 100,000.)

Both scripts behind every number in this post (the Python and Node versions, plus the resize-point tracer and the packed/holey comparison) are packaged in arrays-ops-benchmark.zip, attached to this post.

Back to the Bug

The loop at the top of this post wasn't a trick question. It's the single most common way arrays bite working developers, in any language that has them, and it only looks mysterious until you've internalized what deletion actually costs.

Once you know an array is a contiguous block, and that removing from the middle means physically sliding everything after it, the loop's behavior stops being surprising. It's not broken. It's doing exactly what shifting a block of memory always does. The bug was ever expecting the cursor to notice.

Try it yourself before the next post: take the backward-iteration fix above, and instead of removing values under 50, remove every duplicate value from a list, keeping just the first occurrence of each. Same shifting mechanics, one extra piece of state to track. It's a good gut-check for whether the mental model actually stuck.

Originally published on ZyVOP

💡 For more articles like this, subscribe to the ZyVOP newsletter!