Blog ;Jul 2026 ;2 min read

When Big-O Lies #

Asymptotic complexity is a promise about behavior at infinity. Most of my code never runs there — it runs at n = 4,000 on a Tuesday, and the constants I dropped are the whole story.

There’s a particular kind of confidence that comes from writing O(n log n) in a design doc. It feels like a proof. And it is one — about a limit you will, in practice, never reach.¹ The trouble starts when we treat the asymptote as advice for the machine in front of us.

Last week I replaced a “slow” quadratic scan with a “fast” sort-then-sweep. The theory was unimpeachable. The result was slower — for every realistic input we actually saw.

The measurement #

Here’s the inner loop I started with. The two highlighted lines are the base case — the part I assumed didn’t matter, and the part the profiler kept pointing at.

func Fibonacci(n int) []int {
    seq := make([]int, n)
    for i := range seq {
        if i < 2 {
            seq[i] = i // base case
            continue
        }
        seq[i] = seq[i-1] + seq[i-2]
    }
    return seq
}

Runtime is not one number, it’s a curve with a shape. A more honest model keeps the constants that O-notation throws away:

When $c_1$ hides a cache miss and $c_2$ is a tight, predictable stride, the linear term wins for every $n<{10}^6$ you’ll ever feed it.

A cost model, not a verdict #

Premature optimization is the root of all evil — but so is treating a limit theorem as a benchmark.

So now I hold two numbers in my head before I reach for a cleverer algorithm:

• The asymptotic class — does this fall off a cliff as inputs grow?
• The constant — what does it actually cost at the size I ship?

The rule I settled on #

Measure first, at the real input size, on the real hardware. Let the asymptote decide only when the two curves actually cross — and then write down where they crossed, because the next person (usually me) will want the number, not the theorem.