Visual walkthrough — Big-O notation — formal definition, mathematical
Before any symbol, agree on the drawing board.
Step 0 — The picture we draw everything on
WHAT. We plot input size along a horizontal line and cost (number of steps) along a vertical line. Every algorithm becomes a curve on this board: pick an input size, look up how many steps it takes, mark the dot, join the dots.
WHY. Complexity is about shape as inputs grow. A curve makes "grows" literally a direction — up-and-to-the-right — so "grows faster" becomes "climbs steeper", something your eyes can judge.
PICTURE. The horizontal axis is (input size: how many items). The vertical axis is the number of steps. We only ever look to the right, because we care about big .
Step 1 — Why a raw " under " comparison is unfair
WHAT. Draw and the reference . The cost curve sits above everywhere.
WHY. If we demanded literally, then would "grow faster than" — but they have the same shape (both straight lines through the origin). The only difference is the number , which comes from your machine, compiler, or coffee level. We must not let that number decide the verdict.
PICTURE. Two straight lines from the origin. Same tilt-family, different steepness. The gap between them is a constant stretch, not a change of shape.
So the naive test fails. We need a knob that can lift the reference curve to swallow constant factors.
Step 2 — Introducing : the vertical stretch knob
WHAT. Multiply the reference by a constant: draw for . Now sits on top of — it catches it.
WHY. Multiplying by scales the whole reference curve upward without changing its shape. That's exactly the freedom we wanted: any constant factor hiding inside can be matched by choosing big enough. The symbol is the "ignore constant factors" rule made into a number.
PICTURE. Start with the plain reference (dashed). Then turn the knob to : the whole amber curve scales upward by a factor of until it lands exactly on the cyan cost curve and catches it.
Step 3 — When one is not enough: the crossing point
WHAT. Now let and . Pick . Near the left the constant pokes above . Because the two lines are parallel, stays above everywhere — so the bound is never true with this .
WHY. Small inputs are noisy — setup costs, that stray — and we genuinely don't care about them. We only care how things scale when is huge. So we need a second freedom: permission to ignore the left side of the board (and, as Step 4 shows, a slightly bigger ).
PICTURE. The cyan runs a constant above the amber . The gap never closes.
Step 4 — Introducing : the "start caring here" line
WHAT. Draw a vertical line and call its position . We only require the inequality to the right of . Everything left of it is forgiven.
WHY. is the threshold: "past here the bound holds." It lets small- misbehaviour (the bump) fall outside the region we judge. Combined with , we now have both knobs the definition needs.
For : choose . Then
\qquad\text{for all } n \ge \underbrace{7}_{n_0}.$$ - $3n+7$ — the true cost $f(n)$. - the swap $7 \to n$ — legal *only* to the right of $n_0 = 7$; this is what $n_0$ buys us. - $4n = c\,g$ with $c = 4$ — the stretched reference that now sits on top. **PICTURE.** Shade the region right of $n_0 = 7$ in cyan (the "judged zone"); gray-out the left. Inside the cyan zone the amber $4n$ is always above $f$. ![[deepdives/dd-coding-3.1.01-d2-s05.png]] > [!definition] The full statement, now fully earned > $$f(n) = O(g(n)) \;\iff\; \exists\, c > 0,\ \exists\, n_0 \ge 0 :\quad 0 \le f(n) \le c\cdot g(n)\ \text{ for all } n \ge n_0.$$ > - $f(n) = O(g(n))$ — read "$f$ is Big-O of $g$." The "$=$" is an ==abuse of notation==; the honest > reading is set membership, $f \in O(g)$, i.e. $f$ belongs to the family of functions capped by $g$. > - $\exists\, c > 0,\ \exists\, n_0 \ge 0$ — *there exist* a stretch knob $c$ and a threshold $n_0$. > You only need **one** working pair; that's what "$\exists$" demands. > - $0 \le f(n)$ — costs are never negative (steps can't be negative). > - $f(n) \le c\,g(n)$ — real cost stays under the stretched reference. > - $\forall\, n \ge n_0$ — but only once we're past the threshold. > Two knobs, $c$ (Step 2) and $n_0$ (Step 4), make it true. **Existence of one working pair is the > whole proof.** See [[Limits and infinity (Calculus)|the limit view]] for the $n\to\infty$ story. --- ## Step 5 — Why the bound is *one-sided* (upper only) **WHAT.** Draw $f(n) = n$ against $g(n) = n^2$ with $c = 1$. For $n \ge 1$, the parabola $n^2$ towers over the line $n$. So $n = O(n^2)$ is **true** — even though $n^2$ grows *strictly faster*. **WHY.** Big-O only claims $f$ stays *under* $c\,g$. It never claims they're close. So a function can be Big-O of something wildly bigger — the bound is legal but **loose**. The $\le$ points one way on purpose; it's a ceiling, not a match. For a *matching* ceiling-and-floor, that's [[Big-Theta notation — tight bound|Big-Theta]]; for the floor alone, [[Big-Omega notation — lower bound|Big-Omega]]. **PICTURE.** A gentle straight line $f=n$ crawling near the axis while $g=n^2$ rockets up. Huge gap = loose bound, still valid. ![[deepdives/dd-coding-3.1.01-d2-s06.png]] --- ## Step 6 — The degenerate/failing case: no $c$ can catch it **WHAT.** Try to make $n^2 = O(n)$. Suppose some $c$ works: $n^2 \le c\,n$ for all large $n$. Divide both sides by $n > 0$ (allowed because $g(n) = n$ is strictly positive for $n \ge 1$): $$n \;\le\; c \qquad\text{for all } n \ge n_0.$$ - left side $n$ — grows without bound. - right side $c$ — a *frozen* number. **WHY.** A growing thing cannot stay below a fixed thing forever. As soon as $n > c$, the inequality snaps. So **no** $(c, n_0)$ pair exists — this is how you *disprove* a Big-O claim: assume it, then push $n \to \infty$ until the fixed $c$ is overtaken. **PICTURE.** The parabola $n^2$ pierces straight *through* every amber line $c\,n$ you draw — draw three candidate lines $c = 2, 5, 10$, each one crossed and left behind by the climbing parabola. ![[deepdives/dd-coding-3.1.01-d2-s07.png]] > [!mistake] "I just need to pick a *bigger* $c$." > **Why it feels right:** bigger $c$ lifts the amber line higher, catching more. > **The fix:** No *finite* $c$ works, because $n$ eventually beats **any** fixed number. A steeper > line still has fixed steepness; a parabola's steepness keeps increasing. Shape beats constant. > This is the same reason $2^n \ne O(n^{100})$ — see [[Asymptotic growth rates ordering]]. --- ## The one-picture summary Everything at once: the true cost $f$ (cyan), the stretched reference $c\,g$ (amber) catching it, and the threshold line $n_0$ after which $f$ never escapes. Left of $n_0$: ignored. Right of $n_0$: $f \le c\,g$ forever. *That single geometric fact — plus the "$\exists\, c, n_0$" that names the two knobs — is Big-O.* ![[deepdives/dd-coding-3.1.01-d2-s08.png]] > [!recall]- Feynman retelling — the whole walkthrough in plain words > I'm racing my algorithm's cost curve against a simple reference shape. First problem: my curve sits > higher just because of some boring constant (a fast or slow machine). Fix: I'm allowed to **stretch** > the reference upward by any number $c$ I like — that erases constant factors. Second problem: near > the start my curve wiggles above because of tiny setup costs. Fix: I draw a line $n_0$ and say "only > judge me to the right of here" — that erases small-input noise. The words "there exist $c$ and $n_0$" > just mean *I only have to find one winning pair.* Now if my stretched reference stays on top of my > cost curve for all inputs past $n_0$, I win: I write $f = O(g)$, which really means $f$ belongs to > the family of functions capped by $g$. It's a **ceiling**, so it can sit way too high (loose) and > still count — $n$ is $O(n^2)$. But some races are unwinnable: no amount of stretching lets a straight > line cap a parabola, because a growing $n$ eventually blows past any frozen number $c$. Shape always > beats constant. > [!mnemonic] The two knobs > **$c$ lifts, $n_0$ shifts.** Stretch up with $c$; slide the "start caring" line with $n_0$. Find > one pair that works and you're done. --- ## Recall checks What does the "$=$" in $f(n) = O(g(n))$ really mean? ::: Set membership $f \in O(g)$ — it's an abuse of notation, not equality. Which quantifier governs $c$ and $n_0$ in the definition? ::: Existential: $\exists\, c>0,\ \exists\, n_0\ge 0$ — you need only one working pair. What are the domains of $f$ and $g$? ::: $f, g : \mathbb{N} \to \mathbb{R}^{\ge 0}$ (natural-number inputs, non-negative real costs), with $g$ eventually strictly positive. Right knob for constant factors ::: $c$ (vertical stretch multiplier). Right knob for ignoring small inputs ::: $n_0$ (the threshold; judge only $n \ge n_0$). Why must $g(n)$ be eventually positive? ::: So we may divide by $g(n)$ (as in Step 6) without hitting division by zero. Why multiply $g$ by $c$ instead of adding a constant? ::: A fixed addition can't keep pace with a climbing curve; multiplying scales the growth so one $c$ holds forever. Is $n = O(n^2)$? ::: Yes — Big-O is an upper bound, so $f$ may grow strictly slower than $g$ (loose but valid). How do you disprove $n^2 = O(n)$? ::: Assume $n^2 \le c\,n$, divide by $n$ to get $n \le c$, then let $n \to \infty$ to overtake the fixed $c$ — contradiction. --- ## Connections - [[3.1.1 Big-O notation — formal definition, mathematical]] (parent) - [[Big-Omega notation — lower bound]] - [[Big-Theta notation — tight bound]] - [[Little-o and little-omega]] - [[Asymptotic growth rates ordering]] - [[Limits and infinity (Calculus)]] - [[Time Complexity vs Space Complexity]] - [[Master Theorem]]