Visual walkthrough — Tight bounds — Θ notation; lower bounds — Ω notation

---

Step 1 — What are we even comparing? Two curves.

WHAT. We have two functions of $n$ (the input size — how many items your program handles). Call them:

• $f(n)$ — the cost of your algorithm (number of steps it takes).
• $g(n)$ — a clean reference shape we already understand, like $n$, $n^2$, or $n\log n$.

WHY. We never say "this program takes 4000 steps." Machines differ, inputs differ. Instead we ask a shape question: as $n$ gets huge, does $f$ curve up like $g$? Comparing to a known reference $g$ turns a messy count into a clean category.

PICTURE. Look at the two curves below. The coral curve is $f(n)=3n^2+5n+7$. The lavender curve is the reference $g(n)=n^2$. They look like they bend the same way — but coral is higher. Step 2 asks: is that height difference just a constant stretch?

---

Step 2 — The ceiling: scaling $g$ up until it covers $f$.

WHAT. Take the reference $g(n)=n^2$ and multiply it by a constant $c$. That stretches it vertically. Question: is there a stretch $c$ big enough that $c\cdot g(n)$ sits above $f(n)$ forever?

WHY this tool — a constant multiplier. A 2× faster laptop halves every step count. We refuse to let hardware change an algorithm's category. Multiplying $g$ by a constant $c$ is exactly the freedom "ignore constant factors." If some $c$ makes $cg$ a ceiling, then $f$ never outgrows $g$'s shape.

PICTURE. The mint curve below is $15g(n)=15n^2$. Notice it stays above the coral $f$ once we pass a threshold. That threshold has a name: $n_0$. Before $n_0$ we do not care (the "baby photos" — small $n$).

$\underset{\text{cost}}{\underbrace{f(n)}}\le \underset{\text{stretch factor}}{\underbrace{c}}\cdot \underset{\text{reference}}{\underbrace{g(n)}}\text{for all }n\ge \underset{\text{ignore-before-here}}{\underbrace{n_0}}$

Let us prove $c=15$ works. Term by term:

$3n^2+5n+7\le \underset{\text{keep}}{\underbrace{3n^2}}+\underset{5n\le 5n^2}{\underbrace{5n^2}}+\underset{7\le 7n^2}{\underbrace{7n^2}}=15n^2(n\ge 1)$

WHY each replacement is legal: for $n\ge 1$ we have $n\le n^2$ and $1\le n^2$, so replacing $5n$ by $5n^2$ and $7$ by $7n^2$ only makes the right side bigger. A bigger right side still being $\ge$ our left side proves the ceiling.

---

Step 3 — The floor: shrinking $g$ down until $f$ stays above it.

WHAT. Now do the mirror image. Multiply $g$ by a (possibly smaller) constant $c_1$ and ask: does $f(n)$ stay above $c_{1}g(n)$ forever?

WHY. The ceiling forbids $f$ from being slower than $g$'s shape. But a ceiling alone is a loose promise — anything below it also fits. To pin $f$ we also need a floor that forbids $f$ from being secretly faster. Flip the inequality and you have the lower-bound question.

PICTURE. The butter curve below is $3g(n)=3n^2$. The coral $f$ sits on or above it everywhere (for $n\ge 0$). So $g$ acts as a floor with $c_1=3$.

$\underset{\text{shrink factor}}{\underbrace{c_1}}\cdot \underset{\text{reference}}{\underbrace{g(n)}}\le \underset{\text{cost}}{\underbrace{f(n)}}\forall n\ge n_0$

The proof is even easier than the ceiling:

$3n^2+5n+7\ge 3n^2(n\ge 0)$

WHY: the dropped terms $5n$ and $7$ are positive, so throwing them away only shrinks the left side. If the shrunken thing is still $\ge 3n^2$, so is the full thing.

---

Step 4 — Squeeze both together: the tight bound $\Theta$.

WHAT. Stack Step 2 and Step 3 on one picture. The floor $3n^2$ is below, the ceiling $15n^2$ is above, and $f$ is trapped in the band between them.

WHY. When the same shape $g$ works as both floor and ceiling (with two constants), $f$ can neither escape upward nor sink downward — its growth is $g$'s growth, exactly. That "trapped between two copies of one shape" is precisely $\Theta$.

PICTURE. The shaded lavender band below is everything between $3n^2$ and $15n^2$. The coral $f$ lives inside it forever past $n_0=1$. Trapped = tight.

$0\le \underset{\text{floor (Step 3)}}{\underbrace{c_{1}g(n)}}\le \underset{\text{cost}}{\underbrace{f(n)}}\le \underset{\text{ceiling (Step 2)}}{\underbrace{c_{2}g(n)}}\forall n\ge n_0$

Plugging in our proven constants: $c_1=3$, $c_2=15$, $n_0=1$, giving $3n^2\le f(n)\le 15n^2$.

---

Step 5 — A faster test: divide the curves.

WHAT. Proving constants by hand is slow. Instead, form the ratio $f(n)/g(n)$ and let $n\to \infty$. Call the result $L$.

WHY this tool — the limit. The band picture says $f$ and $g$ differ by a bounded constant factor. The ratio $f/g$ is that factor at each $n$. If the ratio settles to a finite nonzero number, the factor is bounded — that is exactly the $\Theta$ sandwich, read off in one shot. This is why Limits and L'Hôpital's rule powers the shortcut.

PICTURE. Below, $f(n)/g(n)=\frac{3n^2+5n+7}{n^2}=3+\frac{5}{n}+\frac{7}{n^2}$. Watch it glide down toward the dashed line $L=3$: a finite, nonzero limit.

\begin{cases} L=0 & f=O(g)\ \text{but not}\ \Omega(g)\ \ (\text{strictly smaller})\\[2pt] 0<L<\infty & f=\Theta(g)\ \ (\text{same shape!})\\[2pt] L=\infty & f=\Omega(g)\ \text{but not}\ O(g)\ \ (\text{strictly larger}) \end{cases}$$ Our $L=3$ lands in the middle row: $f=\Theta(n^2)$. Same verdict as the hand proof, far less work. (See [[Asymptotic comparison of functions]] for the $o$ and $\omega$ siblings at $L=0$ and $L=\infty$.) --- ## Step 6 — Degenerate case: when NO single $\Theta$ exists. **WHAT.** Try $f(n)=n^2$ against $g(n)=n$. Can $n$ be a *ceiling* for $n^2$? Suppose $n^2\le c\,n$. Divide by $n>0$: $$n \le c$$ **WHY this breaks.** This must hold for **all** large $n$. But no fixed number $c$ is bigger than every $n$ — pick $n=c+1$ and it fails. So **no ceiling constant exists**: $n^2\ne O(n)$. Yet $n^2\ge 1\cdot n$ for $n\ge 1$, so the *floor* holds: $n^2=\Omega(n)$. Floor yes, ceiling no ⇒ **not tight**. **PICTURE.** Below, every stretched line $c\,n$ (three of them) is eventually overtaken by $n^2$. There is no line high enough forever — the ratio $n^2/n=n$ runs off to $\infty$ (that is the $L=\infty$ row of Step 5). ![[deepdives/dd-coding-3.1.06-d2-s06.png]] > [!mistake] "Every algorithm has a $\Theta$." > **Why it feels right:** functions usually have a tidy shape. **Truth:** if best and worst case grow in *different orders*, no single $\Theta$ covers the whole runtime. Insertion sort is best $\Theta(n)$, worst $\Theta(n^2)$ — overall only $O(n^2)$ and $\Omega(n)$. **Fix:** state $\Theta$ *per case*, or bound the spread with $O$ and $\Omega$. See [[Best, worst, and average case analysis]]. --- ## Step 7 — The other degenerate axis: a *problem's* floor. **WHAT.** $\Omega$ can bound a whole **problem**, not just one algorithm. Comparison-based sorting needs $\Omega(n\log n)$ comparisons — a floor under **every possible** sorting algorithm. **WHY it matters.** A [[Decision trees and sorting lower bound|decision tree]] with $n!$ leaf outcomes (all orderings) has height at least $\log_2(n!)=\Theta(n\log n)$, and height = worst-case comparisons. So *no cleverness* can beat $n\log n$. Merge sort *achieves* $O(n\log n)$ — its ceiling meets the problem's floor, so merge sort is **optimal**: $\Theta(n\log n)$. ([[Master Theorem]] confirms merge sort's $\Theta(n\log n)$ from its recurrence.) **PICTURE.** Two brackets meeting: the problem's floor $\Omega(n\log n)$ pushing up, merge sort's ceiling $O(n\log n)$ pushing down, kissing at the optimal line. ![[deepdives/dd-coding-3.1.06-d2-s07.png]] --- ## The one-picture summary ![[deepdives/dd-coding-3.1.06-d2-s08.png]] One reference shape $g$, stretched two ways, traps the cost $f$ in a band — that band **is** $\Theta$. Loosen only the top → $O$. Loosen only the bottom → $\Omega$. Split the curves and take a limit → the verdict falls out as $L$. > [!recall]- Feynman: tell it like a story > I have a mystery cost curve $f$ and a plain reference $g$. First I stretch $g$ upward by a fudge factor $c_2$ until my copy sits *over* $f$ forever — that copy is a **ceiling**, and "there is such a ceiling" is Big-$O$. Then I shrink $g$ by $c_1$ so its copy slides *under* $f$ forever — a **floor**, called $\Omega$. If the same simple $g$ gives me both a floor and a ceiling, then $f$ is caught in a narrow band and I know its growth *exactly* — that is $\Theta$. Lazy trick: instead of building floors and ceilings by hand, I just divide $f$ by $g$ and see where the ratio settles. Settles at zero? $g$ is way bigger, only a ceiling. Runs off to infinity? $g$ is way smaller, only a floor. Settles at a nice middle number? Same shape — $\Theta$. And two warnings I keep taped to my monitor: (1) these three symbols are about *growth*, not about best/worst case — that's a whole different choice. (2) When best and worst grow differently, there is simply no single $\Theta$ to give. > [!recall]- Quick self-check > If $\lim f/g = 7$, which bound? ::: $\Theta(g)$ — finite nonzero limit means same shape. > Why does $n^2\ne O(n)$? ::: $n^2\le cn$ forces $n\le c$, impossible for all large $n$. > What does the shaded band in Step 4 represent? ::: every value between $c_1 g$ and $c_2 g$ — the $\Theta$ trap. > Problem lower bound for comparison sort? ::: $\Omega(n\log n)$ from decision-tree height $\log_2(n!)$. ## Connections - [[Big-O notation — upper bounds]] — the ceiling half, alone. - [[Best, worst, and average case analysis]] — the *other axis* the mistakes confuse. - [[Master Theorem]] — hands you $\Theta$ for divide-and-conquer recurrences. - [[Decision trees and sorting lower bound]] — the $\Omega(n\log n)$ proof of Step 7. - [[Limits and L'Hôpital's rule]] — powers the Step 5 ratio test. - [[Asymptotic comparison of functions]] — $o$ and $\omega$ at $L=0$ and $L=\infty$.