asymptotic-analysis

Sat Apr 04 2026

What's Vague About "Big O"

I knew the labels: $O(n)$ is linear, $O(\log n)$ is logarithmic, $O(2^n)$ is exponential. I could rank them. But I couldn't explain what asymptotic analysis is actually doing, or why the formal definitions are written the way they are. Why do we throw away constants? What's the $n_0$ in the definition? Why is there both a "Big O" and a "little o"?

The missing piece was connecting asymptotic notation to derivatives.

The Slope Perspective

Asymptotic analysis compares how fast the slopes of two functions grow. Given $f(n)$ and $g(n)$, compute their derivatives $f'(n)$ and $g'(n)$. Whichever derivative grows faster will eventually dominate, regardless of what happens at small inputs.

Three cases:

• Constant slope ($f(n) = n$, so $f'(n) = 1$): effort grows steadily. Each additional input costs the same.
• Accelerating slope ($f(n) = n^2$, so $f'(n) = 2n$): effort accelerates. Each additional input costs more than the last.
• Decelerating slope ($f(n) = \log n$, so $f'(n) = 1/n$): effort flattens out. Even for a trillion inputs, $\log_2(10^{12}) \approx 40$.

This is the whole game. When we say $n^2$ "grows faster" than $100n$, we mean the slope of $n^2$ (which is $2n$) eventually outpaces the slope of $100n$ (which is just $100$). No constant multiplier can prevent this, because a growing function always beats a constant.

Why Constants Get Thrown Away

Take $f(n) = 100n$ and $g(n) = n^2$.

At $n = 5$: $f(5) = 500$ and $g(5) = 25$. The linear function looks way worse.

At $n = 1000$: $f(1000) = 10^5$ and $g(1000) = 10^6$. The quadratic function is 10x worse.

The crossover happens at $n = 100$ (where $100n = n^2$). Before that, the constant inflates $f$ above $g$. After that, the accelerating slope of $n^2$ takes over permanently.

The constant 100 only delays the crossover point. It can't prevent it, because $g'(n) = 2n$ keeps growing while $f'(n) = 100$ stays flat. Even $10^9 \cdot n$ would eventually lose to $n^2$, it would just take until $n = 10^9$ for the crossover to happen.

That's why we write $O(n)$ instead of $O(100n)$. The constant changes when the crossover occurs, not whether it occurs.

The Formal Definitions

All four notations classify the relative growth relationship between two functions. The slope perspective connects them all.

Big O ($O$): the loose ceiling ($\le$). $f(n)$ is $O(g(n))$ if there exist constants $c$ and $n_0$ such that for all $n \ge n_0$: $f(n) \le c \cdot g(n)$.

The $n_0$ is the crossover point. We're saying "I don't care about the messy race at small inputs, I only care about behavior after the curves diverge." The $c$ absorbs the constant factor we're throwing away. This allows ties: $2n$ is $O(n)$ because they have the same growth shape.

Little o ($o$): the strict gap ($<$). $f(n)$ is $o(g(n))$ if $\lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$.

Big O allows two functions with the same growth shape (like $2n$ and $n$). Little o demands that $f$ becomes insignificant compared to $g$. The ratio has to go to zero, not just stay bounded. So $n$ is $o(n^2)$ (linear is negligible compared to quadratic), but $2n$ is NOT $o(n)$ (their ratio is 2, not 0). Little o means $g$'s slope is in a completely higher league.

Big Omega ($\Omega$): the floor ($\ge$). $f(n)$ is $\Omega(g(n))$ if $f(n) \ge c \cdot g(n)$ for all $n > n_0$.

The mirror of Big O. Instead of "won't grow faster than this," it says "won't grow slower than this." In security, we use this to prove a lower bound on the attacker's work: their effort is at least exponential.

Theta ($\Theta$): the exact fit ($=$). $f(n)$ is $\Theta(g(n))$ if it is both $O(g(n))$ and $\Omega(g(n))$.

The growth shape is pinned down exactly. It's both the ceiling and the floor.

Worst case vs average case. Big O usually describes worst-case complexity (Murphy's Law: assume the input is the absolute worst arrangement). Average case measures expected time over a randomly chosen input. In security, worst-case matters because we assume the attacker is brilliant and lucky.

The Caveat: Asymptotics vs Practice

An algorithm that is asymptotically better isn't always better in practice. If we're only processing 50 items, an $O(n \log n)$ algorithm with a constant factor of 1000 is slower than an $O(n^2)$ algorithm with a constant factor of 1. The constants we threw away dominate at small inputs.

Asymptotic analysis assumes $n$ is massive. For small or moderate $n$, you have to look at the actual constants and benchmark.

Where This Shows Up in Security

Cryptographic security is built on an asymmetric gap between two growth curves. We want the legitimate user's effort to be polynomial ($O(n)$ or $O(\log n)$), while forcing the attacker into exponential effort ($O(2^n)$).

Adding 1 bit to a key doubles the attacker's work ($2^{n+1} = 2 \cdot 2^n$), but barely changes the user's effort. That's the asymmetry.

In the formal notation: the user's effort is $o$ of the attacker's effort (strict gap, not just Big O). The ratio $\frac{\log n}{2^n} \to 0$, so the user becomes negligible compared to the attacker's workload as $n$ grows.

The threat is shortcuts. If someone discovers an $O(n^3)$ algorithm for factoring (replacing the current exponential methods), the gap collapses. Both user and attacker would be in polynomial time, and the "wall" disappears. This is exactly the quantum computing concern with RSA.

For how this asymptotic gap gets formalized into security definitions, see why-negligible-funcs (negligible functions are the functions that shrink faster than any inverse polynomial, making polynomial repetition unable to amplify success) and hardness-assumption (the assumption that no polynomial-time algorithm can solve the underlying problem).