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

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.

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

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

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)

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

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

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

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

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.