Big-O notation — formal definition, mathematical: Worked examples

The scenario matrix

Before solving, let us name the shapes of problem that exist. Every worked example below is tagged with the cell it hits.

Cell	Case class	What makes it different	Example that covers it
A	Linear + constant	Small term absorbed into big term	Ex 1
B	Polynomial, several terms	Push every low power up to the top	Ex 2
C	Loose upper bound (true but not tight)	$f$ grows strictly slower than $g$	Ex 3
D	Disproof (no $c, n_{0}$ exist)	Ratio $\to \infty$ , contradiction	Ex 4
E	Degenerate / zero-ish input	$g (n) = 0$ somewhere, or $f$ constant	Ex 5
F	Logarithm & log-vs-power	New tool: $lo g n$ grows slower than any $n^{ε}$	Ex 6
G	Exponential vs polynomial (limiting)	Growth-rate showdown at infinity	Ex 7
H	Real-world word problem	Translate code/story into $f (n)$	Ex 8
I	Exam twist (sum & product rules)	Combine two bounds correctly	Ex 9

Figure — Big-O notation — formal definition, mathematical

The figure above is the map we return to in Ex 3: any curve above $f$ is a valid Big-O ceiling. The tight ceiling ( $O (n)$ , chalk-blue) hugs $f$ with a gap that stays proportional; the loose ceiling ( $O (n^{2})$ , chalk-pink) sits above $f$ with a gap that explodes. Both are true Big-O statements — that is the whole subtlety this page drills. Look at how the pink gap widens in the figure while the blue gap does not; that picture is the difference between "loose" and "tight."

Ex 1 — Cell A: linear plus a constant

Worked example Prove

$6 n + 20 = O (n)$ Forecast: Guess a value of $c$ before reading on. (Hint: it will be a little bigger than $6$ .)

Goal: find $c > 0, n_{0} \geq 0$ with $6 n + 20 \leq c n$ for all $n \geq n_{0}$ .

Step 1 — trap the constant term under the linear term. Why this step? The definition lets us pick any threshold $n_{0}$ . If we insist $n \geq 20$ , then $20 \leq n$ , and now the annoying constant $20$ is bounded by something proportional to $n$ — which is what we need, because the right-hand side $c n$ is also proportional to $n$ . $6 n + 20 \leq 6 n + n = 7 n (n \geq 20) .$

Step 2 — read off the constants. Why this step? The right side is now literally $7 \cdot n = c g (n)$ with $g (n) = n$ . We just match the pattern. $c = 7, n_{0} = 20.$

Verify: Plug $n = 20$ : left $= 6 (20) + 20 = 140$ , right $= 7 (20) = 140$ . Equal — the bound just holds at the threshold. For $n = 100$ : left $= 620$ , right $= 700$ , and $620 \leq 700$ . ✓ (Other choices work too — e.g. $c = 26, n_{0} = 1$ gives $6 (1) + 20 = 26 \leq 26 (1)$ . You only need one.)

Ex 2 — Cell B: a full polynomial

Ex 3 — Cell C: a loose but true bound

Worked example Prove

$7 n + 5 = O (n^{2})$ and explain why it is loose Forecast: Is this true? Is it tight? Answer both before reading.

Goal: $7 n + 5 \leq c n^{2}$ for $n \geq n_{0}$ .

Step 1 — bound each term by $n^{2}$ . Why this step? We are aiming at a bigger ceiling ( $n^{2}$ , not $n$ ), so the algebra is even easier — anything linear or constant is eventually swamped by a square. For $n \geq 1$ : $7 n \leq 7 n^{2}$ and $5 \leq 5 n^{2}$ . $7 n + 5 \leq 7 n^{2} + 5 n^{2} = 12 n^{2} (n \geq 1) .$

Step 2 — read off constants. $c = 12, n_{0} = 1.$

Step 3 — why is this loose? Why this step? "Loose" means $f$ grows strictly slower than the ceiling $g$ . This is exactly the chalk-pink curve in the map figure (s01): the ratio $\frac{7 n + 5}{n ^{2}} \to 0$ as $n \to \infty$ — the gap between $f$ and $c g$ widens forever (watch the pink gap explode in that figure). A tight bound (where the ratio stays bounded away from $0$ , the chalk-blue $O (n)$ curve) would be the tightest honest ceiling. So $7 n + 5 = O (n^{2})$ is true but wasteful; it belongs to the "true but not tight" cell. For tight bounds you use Big-Theta notation — tight bound.

Verify: At $n = 1$ : left $= 12$ , right $= 12 (1) = 12$ , equal. At $n = 10$ : left $= 75$ , right $= 1200$ — enormous slack, exactly the looseness. ✓

Ex 4 — Cell D: disproving a claim

Worked example DISPROVE

$n^{3} = O (n^{2})$ Forecast: Do you expect this to hold? (A cube versus a square...) Decide, then prove your instinct.

Suppose (for contradiction) it held: there would exist $c > 0, n_{0}$ with $n^{3} \leq c n^{2}$ for all $n \geq n_{0}$ .

Step 1 — divide out the common power. Why this step? Both sides carry $n^{2}$ . For $n > 0$ we can divide safely (dividing by a positive number keeps the inequality direction). This isolates the growing part. $n^{3} \leq c n^{2} ⟹ n \leq c (n > 0) .$

Step 2 — hit it with $n \to \infty$ . Why this step? $c$ is a fixed constant, chosen once. But $n$ is allowed to grow without bound. The instant $n > c$ (say $n = ⌈ c ⌉ + 1$ ), the inequality $n \leq c$ is false — yet the definition demanded it hold for all $n \geq n_{0}$ . Contradiction. $∴ n^{3} \neq = O (n^{2}) .$

Verify: Take any candidate, e.g. $c = 1000$ . It fails at $n = 1001$ : $100 1^{3} = 1.003 \times 1 0^{9}$ vs $1000 \cdot 100 1^{2} = 1.002 \times 1 0^{9}$ — the cube has overtaken. No finite $c$ survives. ✓ Disproof recipe: show $\frac{f ( n )}{g ( n )} \to \infty$ ; then no constant ceiling can exist. (Formally this is a limit argument — see Limits and infinity (Calculus).)

Ex 5 — Cell E: degenerate / constant / zero inputs

Worked example Two edge cases: (a)

$f (n) = 42$ constant; (b) careful with $g (n)$ that can be $0$ Forecast: Is a constant function $O (1)$ ? And can we write $O (n^{2})$ if $g$ is ever zero?

Part (a): show $42 = O (1)$ . Why this matters: $g (n) = 1$ is the "flat" function — being $O (1)$ means "cost doesn't grow at all." A constant-time algorithm lives here. Step 1. We need $42 \leq c \cdot 1$ for $n \geq n_{0}$ . Choose $c = 42$ (or anything $\geq 42$ ) and $n_{0} = 0$ . Why: $42 \leq 42$ holds for every $n$ , so no threshold is even needed. $c = 42, n_{0} = 0.$

Part (b): the zero-input trap. Why this step? The definition demands $0 \leq f (n) \leq c g (n)$ . If $g (n_{bad}) = 0$ at some point inside our allowed range while $f (n_{bad}) > 0$ , the bound $f \leq c \cdot 0 = 0$ is impossible there. This is exactly why $n_{0}$ exists: we push the threshold past the degenerate point. Example: is $n = O (n^{2})$ ? At $n = 0$ , $g (0) = 0$ but $f (0) = 0$ too, so $0 \leq 0$ holds. Take $c = 1, n_{0} = 1$ : for $n \geq 1$ , $n \leq n^{2}$ . ✓ The one dangerous point ( $n = 0$ ) is harmless here because $f (0) = 0$ as well. Rule: if $f$ is positive where $g$ is zero, raise $n_{0}$ above that point — that is the degenerate-input fix.

Verify: (a) at $n = 1 0^{6}$ , $42 \leq 42$ . ✓ (b) at $n = 1$ : $1 \leq 1$ ; at $n = 2$ : $2 \leq 4$ . ✓

Ex 6 — Cell F: logarithms enter

Worked example Prove

$lo g_{2} n = O (n)$ , and note $n = O (n lo g_{2} n)$ Forecast: Does $lo g n$ grow slower or faster than $n$ ? Picture the two curves before deciding.

Why the tool "logarithm"? A logarithm answers "how many times must I double to reach $n$ ?" — it is the inverse of exponentiation. It shows up whenever an algorithm halves its problem each step (binary search, balanced trees). It grows, but agonisingly slowly.

Step 1 — the key fact: $lo g_{2} n \leq n$ for all $n \geq 1$ . Why this step? We need a clean, provable comparison. The clean route is to prove $n \leq 2^{n}$ for all $n \geq 1$ by induction, then take $lo g_{2}$ of both sides. Base case $n = 1$ : $1 \leq 2^{1} = 2$ . ✓ Inductive step: assume $n \leq 2^{n}$ . Then $n + 1 \leq 2^{n} + 1 \leq 2^{n} + 2^{n} = 2^{n + 1}$ , where the middle step uses $1 \leq 2^{n}$ (true for $n \geq 1$ ). So the claim holds for $n + 1$ . By induction $n \leq 2^{n}$ for all $n \geq 1$ . Now $lo g_{2}$ is an increasing function, so applying it to $n \leq 2^{n}$ preserves the direction: $lo g_{2} n \leq lo g_{2} (2^{n}) = n = 1 \cdot n (n \geq 1) .$ $c = 1, n_{0} = 1.$

Step 2 — the companion loose fact $n = O (n lo g_{2} n)$ . Why this step? Since $lo g_{2} n \geq 1$ once $n \geq 2$ , multiplying $n$ by something $\geq 1$ only makes it bigger: $n \leq n lo g_{2} n$ . So $c = 1, n_{0} = 2$ .

Verify: $lo g_{2} 16 = 4 \leq 16$ . ✓ At $n = 4$ : $lo g_{2} 4 = 2$ , so $n lo g_{2} n = 8 \geq 4 = n$ . ✓ Ordering to memorise (Asymptotic growth rates ordering): $1 ≺ lo g n ≺ n ≺ n lo g n ≺ n^{2} ≺ 2^{n}$ .

Ex 7 — Cell G: exponential vs polynomial (limiting behaviour)

Worked example DISPROVE

$2^{n} = O (n^{10})$ Forecast: Exponential or polynomial — which wins the race to infinity? Bet now.

Why a limit argument here? When both sides grow without bound, comparing them term-by-term is hopeless. The clean tool is the ratio at infinity: if $\frac{f ( n )}{g ( n )} \to \infty$ , then no constant ceiling $c$ can hold $f$ under $c g$ forever. See Limits and infinity (Calculus).

Step 1 — form the ratio. Why this step? Big-O caps $f / g$ by a constant $c$ for large $n$ . So we test whether $f / g$ stays bounded. $R (n) = \frac{2 ^{n}}{n ^{10}} .$

Step 2 — show $R (n) \to \infty$ . Why this step? Exponentials beat polynomials because each $+ 1$ in $n$ multiplies $2^{n}$ by $2$ , while it only nudges $n^{10}$ upward by a shrinking factor. Concretely, $2^{n} / n^{10} \to \infty$ : for large $n$ the numerator's doubling outruns any fixed power. (One can prove it by comparing $ln R (n) = n ln 2 - 10 ln n$ ; the linear term $n ln 2$ dominates $10 ln n$ , so $ln R \to + \infty$ , hence $R \to \infty$ .)

Step 3 — conclude no $c$ exists. Since $R (n)$ eventually exceeds every constant $c$ , there is no valid pair $(c, n_{0})$ . $2^{n} \neq = O (n^{10}) .$

Verify: At $n = 100$ : $2^{100} \approx 1.27 \times 1 0^{30}$ while $10 0^{10} = 1 0^{20}$ ; the ratio is $\approx 1 0^{10}$ , already gigantic and still climbing. ✓ Conversely $n^{10} = O (2^{n})$ — polynomials are Big-O of exponentials (the ceiling is huge but real).

Ex 8 — Cell H: a real-world word problem

Worked example Nested loop cost

A function scans every pair of items in a list of $n$ items, then does $3$ constant-cost checks per pair, plus a one-time setup of $50$ operations. Its step count is $f (n) = 3 \cdot (2 n) + 50 = \frac{3 n ( n - 1 )}{2} + 50 = 1.5 n^{2} - 1.5 n + 50.$ Show $f (n) = O (n^{2})$ . Forecast: What is the shape — linear, quadratic, or worse? Guess from "every pair."

Step 1 — expand and identify the dominant term. Why this step? "Every pair" of $n$ items is $(2 n) = \frac{n ( n - 1 )}{2}$ — quadratic. So the tallest term is $1.5 n^{2}$ ; the $- 1.5 n$ actually helps (it subtracts), and $+ 50$ is a constant.

Step 2 — bound above. Why this step? Dropping the negative term only makes $f$ larger, so $f (n) \leq 1.5 n^{2} + 50$ . Then we need $50 \leq n^{2}$ , which holds precisely for $n \geq 8$ (since $8^{2} = 64 \geq 50$ while $7^{2} = 49 < 50$ ). Use $n_{0} = 8$ : $f (n) \leq 1.5 n^{2} + 50 \leq 1.5 n^{2} + n^{2} = 2.5 n^{2} (n \geq 8) .$ $c = 2.5, n_{0} = 8.$

Verify: At $n = 8$ : $f (8) = 1.5 (64) - 1.5 (8) + 50 = 96 - 12 + 50 = 134$ ; ceiling $= 2.5 (64) = 160$ , and $134 \leq 160$ . ✓ Interpretation: doubling the list roughly quadruples the work — the signature of a nested-pair (quadratic) algorithm. This is a time-complexity statement about the code's steps.

Ex 9 — Cell I: exam twist (sum & product rules together)

Worked example Given

$f_{1} (n) = O (n^{2})$ and $f_{2} (n) = O (n lo g_{2} n)$ , bound $f_{1} (n) + f_{2} (n)$ and $f_{1} (n) \cdot f_{2} (n)$ Forecast: For the sum, which term "wins"? For the product, do exponents add or multiply?

Step 1 — the sum: bigger term wins. Why this step? The sum rule says $O (a) + O (b) = O (max (a, b))$ . Compare $n^{2}$ against $n lo g_{2} n$ : dividing, $\frac{n ^{2}}{n lo g _{2} n} = \frac{n}{lo g _{2} n} \to \infty$ , so $n^{2}$ dominates. Hence $f_{1} + f_{2} = O (n^{2}) .$ Concretely: if $f_{1} \leq c_{1} n^{2}$ and $f_{2} \leq c_{2} n lo g_{2} n \leq c_{2} n^{2}$ (using Ex 6's $lo g_{2} n \leq n$ ), then $f_{1} + f_{2} \leq (c_{1} + c_{2}) n^{2}$ .

Step 2 — the product: multiply the ceilings. Why this step? The product rule: if $f_{1} = O (g_{1})$ and $f_{2} = O (g_{2})$ then $f_{1} f_{2} = O (g_{1} g_{2})$ . Multiply the bounds directly: $f_{1} f_{2} \leq (c_{1} n^{2}) (c_{2} n lo g_{2} n) = c_{1} c_{2} n^{3} lo g_{2} n .$ $f_{1} \cdot f_{2} = O (n^{3} lo g_{2} n) .$

Verify (numeric sanity, using $f_{1} = n^{2}$ , $f_{2} = n lo g_{2} n$ ): at $n = 4$ : $f_{1} = 16$ , $f_{2} = 4 \cdot 2 = 8$ . Sum $= 24 \leq c \cdot 16$ with $c = 2$ ( $= 32$ ). ✓ Product $= 128$ , and $n^{3} lo g_{2} n = 64 \cdot 2 = 128$ , so $128 \leq 1 \cdot 128$ . ✓

Recall

Recall Which cell needs a

raised $n_{0}$ and why? Cell E (degenerate). If $f (n) > 0$ where $g (n) = 0$ , the bound $f \leq c \cdot 0$ is impossible there, so push $n_{0}$ past that point. ::: Raise the threshold above any degenerate input.

Recall Disproof recipe in one line

Show the ratio $f (n) / g (n) \to \infty$ ; then no constant $c$ can cap $f$ under $c g$ . ::: Ratio diverges ⇒ not Big-O.

Recall Sum rule vs product rule

For the sum, keep the maximum term ( $O (n^{2}) + O (n lo g n) = O (n^{2})$ ). For the product, multiply the two ceilings ( $O (n^{2}) \cdot O (n lo g n) = O (n^{3} lo g n)$ ). ::: Max for sums, multiply for products.

Connections

Parent: Big-O — formal definition (mathematical)
Big-Omega notation — lower bound
Big-Theta notation — tight bound
Little-o and little-omega
Asymptotic growth rates ordering
Time Complexity vs Space Complexity
Master Theorem
Limits and infinity (Calculus)

Worked examples — Big-O notation — formal definition, mathematical

The scenario matrix

Ex 1 — Cell A: linear plus a constant

Ex 2 — Cell B: a full polynomial

Ex 3 — Cell C: a loose but true bound

Ex 4 — Cell D: disproving a claim

Ex 5 — Cell E: degenerate / constant / zero inputs

Ex 6 — Cell F: logarithms enter

Ex 7 — Cell G: exponential vs polynomial (limiting behaviour)

Ex 8 — Cell H: a real-world word problem

Ex 9 — Cell I: exam twist (sum & product rules together)

Recall

Connections

Case Map