Big-O Notation: Formal Definition & Growth Rates

Algorithms & Complexity

Chapter 2 · Big-O Notation: Formal Definition & Growth Rates

Chapter 1 used Big-O informally — "O(n²)" as a label for "the work grows like the square of the input." This chapter makes that label precise, with a real formal definition, and builds the full ranked ladder of complexity classes it describes.

The Formal Definition

Big-O, formally

f(n) = O(g(n)) if there exist positive constants c and n₀ such that f(n) ≤ c·g(n) for all n ≥ n₀.

In plain terms: f(n) is O(g(n)) if, past some point (n₀), f(n) never grows faster than a constant multiple of g(n). Big-O describes an upper bound on growth — "grows no faster than" — ignoring exactly how much faster or slower below that bound the real behavior is, and ignoring everything that happens before n₀.

Verifying the Definition With Real Numbers

Claim: f(n) = 3n² + 5n + 100 is O(n²). Trying c = 4:

n	f(n) = 3n²+5n+100	4n²	f(n) ≤ 4n²?
11	518	484	No
12	592	576	No
13	672	676	Yes
14	758	784	Yes

With c = 4 and n₀ = 13, the definition holds for every n ≥ 13 — confirmed exactly at the boundary. f(n) = 3n² + 5n + 100 is genuinely, verifiably O(n²), not just "probably" or "roughly."

The Dominant-Term Rule

In practice, nobody hunts for c and n₀ by hand every time. The shortcut: drop every term except the fastest-growing one, and drop its constant coefficient too.

Dominant-term simplification

3n² + 5n + 100 simplifies to O(n²) — the n² term dominates as n grows; the 5n and 100 terms, and even the leading 3, become irrelevant to the growth shape.

Why this is valid — watch the ratio of the full expression to just n² as n grows:

n	f(n) = 3n²+5n+100	n²	f(n) / n²
10	450	100	4.50
100	30,600	10,000	3.06
1,000	3,005,100	1,000,000	3.005

The ratio converges to a constant, not zero or infinity

As n grows, that ratio settles toward exactly 3 — the leading coefficient. It doesn't shrink to nothing (which would mean n² overstates the growth) or blow up (which would mean n² understates it) — it converges to a fixed multiple, which is precisely what "constant c" means in the formal definition above. The dominant-term shortcut isn't a hand-wave; it's the formal definition, worked out in advance for the general case.

The Ranked Ladder of Common Complexity Classes

Class	Name	Real example
O(1)	Constant	Array index access, hash table lookup
O(log n)	Logarithmic	Binary search (Chapter 1's own example)
O(n)	Linear	A single pass over a list, linear search
O(n log n)	Linearithmic	Efficient sorting — merge sort, average-case quicksort
O(n²)	Quadratic	Nested loops, bubble sort
O(n³)	Cubic	Triple-nested loops, naive matrix multiplication
O(2ⁿ)	Exponential	Naive recursive Fibonacci, generating every subset
O(n!)	Factorial	Generating every permutation, brute-force traveling salesman

Convention: always state the tightest valid bound

Technically, an O(1) algorithm is also, correctly, O(n) — a constant is never larger than a constant multiple of n past some point, so the formal definition holds. But stating "O(n)" for a genuinely constant-time algorithm would be true yet uselessly loose. By strong convention, Big-O is always reported as the smallest (tightest) class that still validly bounds the function — Chapter 4's Big-Theta gives this convention a fully formal footing.

Big-O Verification in Code

def f(n):
    return 3*n**2 + 5*n + 100

def is_O_n_squared(f, c, n0, test_range=range(1, 100)):
    return all(f(n) <= c * n**2 for n in test_range if n >= n0)

print(is_O_n_squared(f, c=4, n0=13))  # True — matches the worked verification above
print(is_O_n_squared(f, c=4, n0=1))   # False — n0=13 is genuinely required, not just convenient

Hands-On Exercises

Exercise 1

Using this chapter's own dominant-term rule, simplify f(n) = 7n³ + 2n² + 50 to its Big-O class. State which terms were dropped and why.

📄 View solution

Exercise 2

Verify f(n) = 2n² + 3n + 10 is O(n²) using c = 3. Find the smallest integer n₀ for which f(n) ≤ 3n² holds for all n ≥ n₀, showing the boundary value where it first becomes true.

📄 View solution

Exercise 3

Rank the following complexity classes from slowest-growing to fastest-growing: O(n²), O(log n), O(1), O(2ⁿ), O(n log n), O(n). Briefly justify the placement of O(n log n) relative to its two neighbors in your ranking.

📄 View solution

Chapter 2 Quick Reference

Formal definition: f(n)=O(g(n)) if f(n) ≤ c·g(n) for some constants c, n₀ and all n ≥ n₀
Dominant-term rule: keep only the fastest-growing term, drop its coefficient — valid because the ratio to that term converges to a constant, never zero or infinity
Ranked classes: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)
By convention, always report the tightest valid Big-O class, even though looser bounds are technically also true
Next chapter: Analyzing loops — from code to Big-O