Chapter 9Complexity Analysisslides.en.pdf:205

Growth Ranking

O(1) ⊂ O(log n) ⊂ O(n) ⊂ O(n²) ⊂ O(nᵏ) ⊂ O(kⁿ)

Theorem 0.5 — Growth ranking

Concept

Growth Ranking Lemma (Lemma 0.5):

O(1) \subset O(\log n) \subset O(n) \subset O(n \log n) \subset O(n^2) \subset O(n^k) \subset O(2^n)

These classes are nested: every constant function is eventually bounded by
every logarithmic function; every logarithmic by every linear; etc.

Why this matters. When you analyze an algorithm, identifying its growth
class lets you compare it to others without doing exact arithmetic. "Is it
better than $O(n^2)$ ?" is a meaningful question; "is it $7n^2$ or
$8n^2$ ?" usually is not.

Reading the chain:
- $O(1)$ : hash table lookup. Independent of $n$ .
- $O(\log n)$ : binary search. Each step halves the problem.
- $O(n)$ : scan a list once.
- $O(n \log n)$ : merge sort, heap sort. Best general-purpose sorting.
- $O(n^2)$ : bubble sort, naive all-pairs.
- $O(n^k)$ : polynomial. Acceptable for small $k$ .
- $O(2^n)$ : subset enumeration. Becomes infeasible fast.

Crucial observation. Polynomial vs. exponential is the cliff. Anything
polynomial is "tractable" for reasonable $n$ (within hardware limits).
Anything exponential hits a wall around $n \approx 50$ .

Proving $O(\log n) \subset O(n)$ : any $f \in O(\log n)$ is bounded by
$c \log n$ . We need $c' n$ for large $n$ . Take $n \geq 2$ : $\log n \leq n$ .
So $c \log n \leq cn \leq c' n$ with $c' = c$ . ✓

Each step in the chain has a similar proof using elementary inequalities.

Animation — big o growth

Transcript — click a line to jump8 cues

0.0sGrowth of Common Functions
0.8sAxes drawn: n on the horizontal, f(n) on the vertical.
1.8sConstant 1: flat baseline.
2.6slog n: barely rises across the entire range.
3.4sn: a steady diagonal line.
4.2sn squared: curves up gently at first, steepens later.
5.0s2 to the n: explodes exponentially and dwarfs every other curve.
6.4sExponential eventually overtakes everything.

Practice — score 100% to advance

Multiple choice

Which is correct:

O(n) \subset O(n \log n)

Which is the fastest growth class in this list?

Why is the polynomial-vs-exponential boundary important?

Binary search is in which class?

O(n^2) \subset O(n^3)

O(2^n) \subset O(n^k)

for any

k

Order the steps

Arrange these proof steps in the correct order using the arrows.

O(n^k)

— polynomial. Tractable for small

k

; large

k

is borderline.

O(\log n)

— logarithmic. Binary search. Doubling

n

adds one step.

O(2^n)

— exponential. Subsets, brute force. Infeasible past

n \approx 50

O(n^2)

— quadratic. All-pairs. Doubling

n

quadruples the work.

O(n \log n)

— log-linear. Merge sort. The classic sorting bound.

O(1)

— constant. Hash table lookup. Independent of

n

O(n)

— linear. Single scan. Doubling

n

doubles the work.

Loading…