Appendix E: Big-O and Complexity Reference

This is the one-page complexity reference for the whole book: the formal definitions of the three asymptotic notations, the growth hierarchy to know by heart, the running times of every algorithm and operation we analyze, and a recipe for reading complexity off code. Everything here is developed and proved in Chapter 14 (notation and loop analysis) and Chapter 19 (recurrences and the Master Theorem); this page is the condensed lookup card. See also Appendix A, which lists $O$, $\Omega$, and $\Theta$ alongside the book's other notation.

A standing convention, carried from Appendix A: $\mathbb{N} = \{0, 1, 2, \dots\}$, and the functions we bound map sizes to nonnegative costs, $f, g : \mathbb{N} \to \mathbb{R}_{\ge 0}$.

E.1 The three notations (formal definitions)

These are the definitions from §14.3, stated identically here. In each, the constants $c$ (or $c_1, c_2$) are positive reals and $n_0$ is a natural number; the pair you exhibit is called the witnesses.

Equivalently, $f(n) = \Theta(g(n))$ means there exist $c_1, c_2 > 0$ and $n_0$ with $$c_1\, g(n) \le f(n) \le c_2\, g(n) \quad \text{for all } n \ge n_0.$$

💡 Intuition: $O$ is a ceiling, $\Omega$ is a floor, $\Theta$ is both at once. To prove an $O$ or $\Omega$ claim, produce one valid witness pair $(c, n_0)$ — the pair is never unique. To disprove an $O$ claim, show no constant $c$ works for all large $n$.

Reading the "$=$". The equals sign in $f(n) = O(g(n))$ is a traditional abuse of notation meaning "$f$ belongs to the set of functions bounded by $g$." Never read it as symmetric: $3n = O(n^2)$ is fine, but $O(n^2) = 3n$ is meaningless, and $n^2 = O(n)$ is false.

Relationships worth memorizing (all from §14.3):

• $\Theta$ is symmetric: $f = \Theta(g)$ iff $g = \Theta(f)$. $O$ is not: $n = O(n^2)$ but $n^2 \ne O(n)$.
• Leading term dominates: a degree-$d$ polynomial $a_d n^d + \dots + a_0$ (with $a_d > 0$) is $\Theta(n^d)$. Drop constants and lower-order terms.
• Sum rule: $f_1 + f_2 = \Theta(\max(g_1, g_2))$. Sequential phases are dominated by the costliest; the cheaper phase vanishes.
• Logs beat powers, powers beat exponentials: for every $k$ and every $\varepsilon > 0$, $\log n = O(n^\varepsilon)$ and $n^k = O(2^n)$. The base of a logarithm is irrelevant ($\log_a n = \Theta(\log_b n)$), so we write $O(\log n)$ with no base.

⚠️ Common Pitfall: $O$ is only an upper bound, so loose statements are still true: an $\Theta(n)$ algorithm "is $O(n^2)$" is correct but uninformative. When an engineer says "this is $O(n^2)$," they usually mean the bound is tight — but only $\Theta$ actually promises tightness.

E.2 The growth hierarchy

From slowest-growing (cheapest) to fastest-growing (most expensive), the classes you will meet for the rest of your career are ordered as follows. Here $f \prec g$ means $f(n) = O(g(n))$ but $g(n) \ne O(f(n))$ — i.e. $g$ genuinely outgrows $f$.

$$\Theta(1) \prec \Theta(\log n) \prec \Theta(n) \prec \Theta(n \log n) \prec \Theta(n^2) \prec \Theta(2^n) \prec \Theta(n!)$$

Two rungs slot in often enough to note: $\Theta(\sqrt{n})$ sits between $\log n$ and $n$ (trial division to $\sqrt{n}$), and $\Theta(n^3)$ sits between $n^2$ and $2^n$ (naive matrix multiplication, Floyd–Warshall). The full ordering is then $$\Theta(1) \prec \Theta(\log n) \prec \Theta(\sqrt{n}) \prec \Theta(n) \prec \Theta(n\log n) \prec \Theta(n^2) \prec \Theta(n^3) \prec \Theta(2^n) \prec \Theta(n!).$$

The tractability line. An algorithm runs in polynomial time if it is $O(n^k)$ for some fixed $k$, and in exponential time if it is $\Omega(c^n)$ for some $c > 1$ (note $n! \ge 2^{n-1}$, so factorial is exponential-or-worse). Polynomial = tractable; exponential = intractable for all but tiny inputs — the dividing line that organizes complexity theory (Chapter 37). Faster hardware does not close the gap: a $1000\times$ faster machine lets an exponential algorithm handle an input only about $\log_2 1000 \approx 10$ elements larger.

🚪 Threshold Concept. Once you compare algorithms by growth class rather than by milliseconds, your judgments stop expiring. A single $\Theta$ class describes how an algorithm scales on hardware not yet invented — which is why "what's the Big-O?" is the first question in every system-design review.

⚠️ Common Pitfall: $n^2$ and $2^n$ look alike and are constantly confused. $n^2$ is polynomial (tractable); $2^n$ is exponential (intractable). At $n = 30$, $n^2 = 900$ while $2^n \approx 10^9$. Read the variable's position: a variable in the exponent means exponential.

E.3 Complexities of the algorithms and operations in this book

Running times of the algorithms analyzed across the book and built into the dmtoolkit package. Unless noted, $n$ is the input size; for graphs, $V = \lvert V\rvert$ and $E = \lvert E\rvert$. "Worst case" unless a column says otherwise.

Searching and sorting

Data-structure operations

Number theory and cryptography (Chapters 22–25)

For integer inputs the size is the number of bits $k$ of the operands, not the integer's value — the distinction that makes RSA secure (§14.2).

Graph algorithms (Chapters 27–34)

Assuming an adjacency-list representation (the right default for sparse graphs).

Recurrences, coding, and combinatorics

🔗 Connection. Several of these meet a matching lower bound, which upgrades "fast" to "optimal": finding a max needs $\ge n-1$ comparisons, so it is $\Theta(n)$ (§14.6); comparison sorting needs $\Omega(n\log n)$, which merge sort attains. A matching upper and lower bound means no algorithm can do asymptotically better.

E.4 How to find the complexity of code

You rarely prove a bound from the definition in daily work; you read it off the structure. The full treatment is §14.4 (loops) and Chapter 19 (recurrences); here is the recipe.

Loops (Chapter 14)

1. Straight-line code (no loops): $\Theta(1)$ — but beware operations that hide loops (list copy, x in some_list, slicing are each $\Theta(n)$, not $\Theta(1)$).
2. A single loop, constant work per pass, $n$ passes: $\Theta(n)$. In general, cost = (number of iterations) $\times$ (work per iteration).
3. Sequential blocks ($A$ then $B$): add, then keep the larger — sum rule, $\Theta(\max)$.
4. Nested loops: multiply the trip counts — but only if they are independent. If the inner bound depends on the outer index, evaluate the sum. The pairwise scan $\sum_{i=0}^{n-1}(n-1-i) = \tfrac{n(n-1)}{2} = \Theta(n^2)$ is the model case.
5. Halving (or thirding) loops: a quantity repeatedly divided by a constant factor until it hits a floor runs $\Theta(\log n)$ times. Repeated halving $\Rightarrow \log$.

⚠️ Common Pitfall: "Two nested loops $\Rightarrow O(n^2)$" is a guess, not a rule. If the inner loop runs a constant number of times, the pair is $\Theta(n)$; if the inner size depends on a different variable $m$, it is $\Theta(nm)$. Always identify the inner loop's actual trip count.

Recurrences (Chapter 19)

A recursive function that makes $a$ calls on inputs of size $n/b$ and does $f(n)$ work to split and combine obeys the divide-and-conquer recurrence $T(n) = a\,T(n/b) + f(n)$ (with $a \ge 1$, $b > 1$). Read $a$, $b$, and $f$ off the code, then apply the Master Theorem (§19.3), comparing $f(n)$ against the watershed $n^{\log_b a}$:

Worked reads: merge sort has $a=2, b=2, f=\Theta(n)$, so $n^{\log_2 2}=n$ matches $f$ — Case 2, $\Theta(n \log n)$. Binary search has $a=1, b=2, f=\Theta(1)$, so $n^{\log_2 1}=1$ matches — Case 2, $\Theta(\log n)$. When the theorem does not apply (unequal splits, non-polynomial $f$), use the recursion-tree or substitution method (§19.2, §19.6). For linear recurrences like Fibonacci's, use the characteristic-equation method of Chapter 18 instead.

🧩 Productive Struggle: Before reading the table again, classify $T(n) = 2T(n/2) + \Theta(n^2)$. (Watershed $n^{\log_2 2} = n$; $f(n) = n^2$ grows faster, so Case 3: $T(n) = \Theta(n^2)$.)

E.5 Quick "identify the complexity" table

Match the code pattern on the left to its growth class. Use this as a first guess, then confirm with §E.4.

🔄 Check Your Understanding 1. A loop for i in range(n) whose body contains a fixed for j in range(8) loop — what class? 2. A function recurses as $T(n) = T(n/2) + \Theta(1)$ — what closed form, and what real algorithm? 3. Is an $O(n^{50})$ algorithm polynomial? Is it "fast"? Are those the same question?

Answers

1. $\Theta(n)$ — the inner loop runs a constant 8 times, so $O(8) = O(1)$ per pass; nested loops are only $\Theta(n^2)$ when the inner count grows with $n$. 2. $\Theta(\log n)$ — this is binary search; by the Master Theorem, $a=1, b=2, f=\Theta(1)$ gives Case 2, $\Theta(\log n)$. 3. It is polynomial (the exponent 50 is a fixed constant), but it is certainly not fast in practice. "Polynomial" is the theoretical tractability line; real-world speed also depends on the exponent and the hidden constants. The two questions are genuinely different — though, conveniently, almost every naturally occurring polynomial algorithm has a small exponent.

See also: Appendix A (full notation table, including $O$, $\Omega$, $\Theta$); Chapter 14 (formal definitions, witness proofs, loop analysis, best/worst/average case, lower bounds); Chapter 19 (divide-and-conquer recurrences, the recursion-tree method, the Master Theorem, and the $O(\log n)$ Fibonacci); Chapter 37 (the P-versus-NP frontier, where the polynomial/exponential line becomes the central question of the field).