Asymptotic Notations
Chapter 3 gave us running times like "a quadratic function of n". This chapter introduces the precise language for such statements — Big-O, Omega, and Theta — which describe how a function grows as the input size approaches infinity. We define each notation, learn to verify or refute claims like f(n) = O(g(n)), see how to use the notations precisely, and finish with the stricter small-o and small-ω and the algebraic properties that make the notations easy to work with.
4.1What is Asymptotic Notation?
Take a simple running time:
f(n) = 2n + 3
How does f(n) grow with n? The term 2n dominates the growth — the constant 3 becomes negligible when n is very large. Asymptotic notation lets us say exactly that, and nothing more: it keeps the dominant term and discards the constants and lower-order noise (recall T(n) = n²/100 + 100n + 7 from Chapter 3, where the n² term won for large n).
4.2Big-O Notation — the Upper Bound
Suppose there are two functions:
f(n) = 2n + 1 g(n) = 3n
f(n) ≤ C · g(n) ∀ n ≥ n₀
- f(n) will not grow faster than g(n);
- g(n) is the upper bound of f(n);
- g(n) should be the closest to f(n) — e.g. for f(n) = 2n + 1 we do not usually take g(n) = nᶜ with c ≥ 2, even though technically 2n + 1 = O(n²) too.
4.3Big-O: Worked Checks
f(n) = 2n² + 3 g(n) = 500n
show answer
Try n = 1000: f(n) = 2,000,003 but C·g(n) with C = 1 gives 500,000 — f(n) > g(n). No fixed constant C rescues this: 2n² eventually outgrows any C·500n, because n²/n = n grows without bound. So f(n) ≠ O(g(n)).
show answer
Suppose: n³ − 100n² = O(n²) ⇒ n³ − 100n² ≤ C·n² for some constant C, large n Divide both sides by n²: ⇒ n − 100 ≤ C ⇒ fails for every n > C + 100
Whatever constant C we pick, the inequality breaks as soon as n exceeds C + 100. Since the definition demands it hold for all n ≥ n₀, no C works: n³ − 100n² ∉ O(n²). Watch this exact failure happen live in the playground below — pick preset 3 and drag C as high as you like.
4.4Try it: The Big-O Playground
The definition says: find one C and one n₀ that make f(n) ≤ C·g(n) forever after. Here you can hunt for them by hand.
4.5Omega (Ω) Notation — the Lower Bound
f(n) ≥ C · g(n) ∀ n ≥ n₀
- Ω-notation characterizes a lower bound on the asymptotic behavior of a function;
- g(n) is the lower bound of f(n);
- g(n) should again be the closest to f(n).
f(n) = log n g(n) = n
show answer
We would need log n ≥ C·n forever after some n₀ — but log n grows far slower than n, so the ratio (log n)/n shrinks to 0 and no positive C survives. f(n) ≠ Ω(n). (The other way works: n = Ω(log n).)
4.6Theta (Θ) Notation — the Tight Bound
C₁ · g(n) ≤ f(n) ≤ C₂ · g(n) ∀ n ≥ n₀
Θ-notation characterizes a tight bound on the asymptotic behavior of a function: g(n) sandwiches f(n) from both sides at once.
4.7Using the Notations Precisely
- E.g. 7n³ + 100n² − 20n + 6 is both O(n³) and Ω(n³), so it is also Θ(n³).
- Linear search to find the largest/smallest element in an array: upper bound O(n) and lower bound Ω(n) (Chapter 3, exercise 3.11 — every element must be checked), so its running time is Θ(n).
True or false? Insertion sort edition
show answer
Θ(n²) claims a tight bound covering all cases — but the best-case running time is linear (Θ(n) on a sorted input). One statement cannot cover all cases with Θ(n²), so the claim is incorrect.
show answer
Restricted to the worst case (reverse-sorted input), the running time is both O(n²) and Ω(n²), hence Θ(n²). Scoping the statement to one case makes the tight bound legitimate.
show answer
Every case — best, worst, or average — takes at least linear time, because the algorithm must at minimum look at each of the n elements once. A lower bound that holds for all cases is a correct (if weak) statement.
4.8Practical Conventions
show answer
Technically we could also say O(n³) — true but less precise — or Θ(3n² + 20n) — true but unnecessarily complex. The convention: the simplest, tightest form wins.
4.9Small-o and Small-ω — Strict Bounds
f(n) < C · g(n) ∀ n ≥ n₀
- o(g(n)) is asymptotically strictly tighter than O(g(n)) — strict inequality, and it must work for every C, not just one.
- For example, 2n = o(n²), but 2n² ≠ o(n²) — a function is never small-o of its own growth rate.
- The same relationship holds between ω(g(n)) and Ω(g(n)): ω is the strict version of Ω.
| Notation | Meaning (intuition) | Analogy |
|---|---|---|
| O | grows no faster than | ≤ |
| Ω | grows no slower than | ≥ |
| Θ | grows at the same rate as | = |
| o | grows strictly slower than | < |
| ω | grows strictly faster than | > |
4.10Properties of Asymptotic Notations
Transitivity
Bounds chain: if f is bounded by g and g by h, then f is bounded by h — for all five notations.
- f(n) = Θ(g(n)) and g(n) = Θ(h(n)) ⟹ f(n) = Θ(h(n))
- f(n) = O(g(n)) and g(n) = O(h(n)) ⟹ f(n) = O(h(n))
- f(n) = Ω(g(n)) and g(n) = Ω(h(n)) ⟹ f(n) = Ω(h(n))
- f(n) = o(g(n)) and g(n) = o(h(n)) ⟹ f(n) = o(h(n))
- f(n) = ω(g(n)) and g(n) = ω(h(n)) ⟹ f(n) = ω(h(n))
Transpose symmetry
An upper bound read backwards is a lower bound:
- f(n) = O(g(n)) ⟷ g(n) = Ω(f(n))
- f(n) = o(g(n)) ⟷ g(n) = ω(f(n))
Two more useful properties
- Reflexivity — every function bounds itself: f(n) = O(f(n)), f(n) = Ω(f(n)), f(n) = Θ(f(n)).
- Symmetry (Θ only) — f(n) = Θ(g(n)) if and only if g(n) = Θ(f(n)). "Same growth rate" is a two-way street; O and Ω are one-way.
4.11Exercises
show answer
"At least" asks for a lower bound, but O gives an upper bound — "at least at most n²" says nothing. Every algorithm trivially satisfies it (even O(1) ones, since "at least O(n²)" excludes nothing). The correct phrasing for the intended meaning is Ω(n²).
show answer
2ⁿ⁺¹ = 2 · 2ⁿ, so with C = 2 the definition holds: yes, 2ⁿ⁺¹ = O(2ⁿ). But 2²ⁿ = (2ⁿ)² = 4ⁿ, and 4ⁿ/2ⁿ = 2ⁿ grows without bound — no constant C can hold it down, so 2²ⁿ ≠ O(2ⁿ). Constant factors in the exponent matter!
show answer
Since n > k, we have n + k < 2n, so (n + k)ᵐ < (2n)ᵐ = 2ᵐ · nᵐ — and 2ᵐ is a constant. Hence (n + k)ᵐ = O(nᵐ) (in fact Θ(nᵐ), since (n + k)ᵐ ≥ nᵐ). Shifting a polynomial's argument by a constant never changes its growth rate.
SUM-ARRAY(A, n) 1 sum = 0 2 for i = 1 to n 3 sum = sum + A[i] 4 return sum
show answer
One loop over n elements doing constant work per element: at most c₁n + c₂ steps (O(n)) and at least n additions (Ω(n)) — both bounds meet, so SUM-ARRAY runs in Θ(n) in every case.
show answer
First simplify g: log n¹⁰ = 10 log n, so g(n) = 10 n log n. Then f/g = n²⁰ log n / (10 n log n) = n¹⁹/10 → ∞. f grows strictly faster: f = ω(g), equivalently g = o(f). (Rule: powers of n dominate powers of log.)
show answer
f(n) = 3n^(3/2) is a polynomial. g(n) contains 2^√n, which is super-polynomial: for any fixed power nᶜ, taking logs gives c log n vs √n, and √n wins. So every polynomial is eventually dwarfed: f = o(g).
show answer
Compare the logarithms: log f = log²n and log g = √n. Since log²n = o(√n) (any power of log loses to any power of n, even √n), we get f = o(g). Quasi-polynomial < exponential-in-√n.
show answer
The worst case is both O(log n) and Ω(log n), so Θ(log n) is correct there. But as a statement about all cases it fails — the best case finds the key at the first mid in Θ(1). For the general case we can only say O(log n) and Ω(1) (exactly the insertion-sort lesson from §4.7).
show answer
Insertion wins while 8n² < 64 n lg n, i.e. n < 8 lg n. Checking integers: at n = 43, 8 lg 43 ≈ 43.4 > 43 (still wins); at n = 44, 8 lg 44 ≈ 43.7 < 44 (loses). So insertion sort beats merge sort for 2 ≤ n ≤ 43 — the reason real libraries switch to insertion sort on small subarrays despite its worse asymptotics.
show answer
We need 100n² < 2ⁿ. At n = 14: 100 · 196 = 19,600 vs 2¹⁴ = 16,384 — exponential still slower? No, 19,600 > 16,384, so the quadratic algorithm is still worse. At n = 15: 100 · 225 = 22,500 vs 2¹⁵ = 32,768 — now 22,500 < 32,768. Answer: n = 15. Exponentials start slow but always win in the end.
show answer
The worst case is Θ(n²), and n² grows strictly slower than nᶠ for any k > 2 — so the worst-case time is o(nᶠ) for every k > 2, e.g. o(n³). Note it is not o(n²): a function is never small-o of its own tight bound.