The five asymptotic notations, stated precisely, plus the standard functions and identities that every later analysis assumes you can manipulate without looking them up.
Chapter 2 said “drop the lower-order terms and the constant” and got away with it. Chapter 3 makes that legitimate. It defines O, Ω, Θ, o, and ω as sets of functions, proves the relationship between them, explains the notational abuses everyone commits, and then collects the standard functions — logarithms, exponentials, factorials, the iterated logarithm — with the identities you need to compare them. It is the most notation-dense chapter in Part I and the one whose contents you will use most often without noticing.
O(n²) as opposed to saying a function is.The running time of insertion sort came out as an² + bn + c, where a, b, and c were sums and differences of eight unknown machine constants. Nobody can use that expression, and nobody should want to: the constants depend on the compiler, the processor, and the mood of the branch predictor. What survives all of that is the n².
Two cautions the chapter is explicit about. Asymptotic statements say nothing about small inputs — an algorithm that is Θ(n lg n) can lose badly to a Θ(n²) one below some threshold, as Chapter 1’s table showed. And the notations are defined for functions whose domain is the natural numbers, since running times are counts; when we write Θ(n²) for a function of a real variable, we mean the restriction to integers.
Start with the strongest of the three, because the other two are halves of it. The key move is that Θ(g(n)) is a set of functions, not a number.
Θ(g(n)) = { f(n) : there exist positive constants c₁, c₂, and n₀
such that 0 ≤ c₁g(n) ≤ f(n) ≤ c₂g(n)
for all n ≥ n₀ }Read it as: past some point n₀, the function f is trapped between two constant multiples of g. We say g(n) is an asymptotically tight bound for f(n).
Three details in that definition earn their place:
c₁, c₂, and n₀ to make the claim true. They may be as large or as small as you like, as long as they are positive and do not depend on n.n ≥ n₀”. The inequality is allowed to fail for finitely many small inputs. This is what “asymptotic” means, and it is why the notation says nothing about small n.0 ≤. This forces f(n) to be non-negative past n₀. CLRS assumes throughout that the functions being bounded are asymptotically non-negative, which running times always are.½n² - 3n = Θ(n²)This is the book’s own example and it is the one to be able to reproduce. We must find c₁, c₂, n₀ with
c₁n² ≤ ½n² - 3n ≤ c₂n² for all n ≥ n₀Divide through by n², which is positive, so the inequalities are preserved:
c₁ ≤ ½ - 3/n ≤ c₂The middle expression increases toward ½ as n grows. So:
½ - 3/n ≤ ½ for every n ≥ 1, so c₂ = ½ works.c₁ = 1/14. Then we need 1/14 ≤ ½ - 3/n, i.e. 3/n ≤ 3/7, i.e. n ≥ 7.So c₁ = 1/14, c₂ = ½, n₀ = 7 verify the claim. Other choices work too; the definition only demands that some triple exists.
p(n) = a₄nᵈ + … + a₁n + a₀ with a₄ > 0, we have p(n) = Θ(nᵈ). The lower-order terms are eventually swamped by the leading one, and the leading coefficient is absorbed into c₁ and c₂. You will almost never need to do the c₁, c₂, n₀ dance in practice — but being able to do it once is what makes the shortcut trustworthy.The same reasoning shows why lower-order terms are discardable in general: they are, by definition, functions that grow more slowly, so past some n₀ their contribution can be covered by adjusting the constants. And a constant function is Θ(1), with n⁰ = 1 the implicit g.
Θ bounds a function from both sides. Often you can only establish, or only care about, the upper side.
O(g(n)) = { f(n) : there exist positive constants c and n₀
such that 0 ≤ f(n) ≤ c·g(n)
for all n ≥ n₀ }g(n) is an asymptotic upper bound for f(n): f grows no faster than g, to within a constant factor.
Since Θ requires both bounds and O only the upper one, Θ(g(n)) ⊆ O(g(n)). Anything tightly bounded is also upper bounded. The converse fails, and that asymmetry is the source of the most common misuse of the notation:
O is an upper bound, not a description. Every one of these is true: n = O(n), n = O(n²), n = O(n¹⁰⁰), n = O(2ⁿ). The last three are true and useless, the way “this flight takes at most a year” is true and useless. When someone says an algorithm is O(n²) they usually mean Θ(n²); when a paper says it, they may well mean only the upper bound, because a matching lower bound was too hard to prove. The distinction matters when comparing two algorithms.The convention in the literature is nonetheless to use O most of the time, for a good reason: an upper bound on the worst case is a guarantee, and a guarantee is what you want from an analysis. Note also that bounding the worst case with O(n²) automatically bounds every case with O(n²), which is not true of Θ. Insertion sort’s running time is O(n²) on all inputs, but it is not Θ(n²) on all inputs — on sorted input it is Θ(n).
Ω(g(n)) = { f(n) : there exist positive constants c and n₀
such that 0 ≤ c·g(n) ≤ f(n)
for all n ≥ n₀ }g(n) is an asymptotic lower bound: f grows at least as fast as g, to within a constant factor.
Ω is how you say an algorithm cannot do better than something. The best-case running time of insertion sort is Ω(n), which is really just the observation that it must at least look at every element. More substantially, Chapter 8 proves that any comparison sort takes Ω(n lg n) comparisons in the worst case — a statement about every possible algorithm of that kind, which is why lower bounds are the harder and more interesting half of the subject.
The definitions are easier to hold onto as three graphs. In each, the shaded relationship only has to hold to the right of n₀.
n₀ the curves may cross freely; the definitions constrain nothing there.f(n) and g(n), we have f(n) = Θ(g(n)) if and only if f(n) = O(g(n)) and f(n) = Ω(g(n)).The proof is immediate from the definitions — the two one-sided inequalities of O and Ω are exactly the two halves of the Θ inequality — but the theorem is the standard proof strategy for tight bounds, and it is used constantly:
To show f(n) = Θ(g(n)):
1. Prove the upper bound f(n) = O(g(n))
2. Prove the lower bound f(n) = Ω(g(n))
3. Cite Theorem 3.1An example the chapter uses: an² + bn + c = Θ(n²) for constants a > 0, b, c. Rather than hunting for c₁ and c₂ simultaneously, bound above by noting every term is at most a constant times n² for large n, bound below by noting the an² term eventually dominates the others, and conclude.
The theorem also explains the standard division of labour in algorithms research. To pin down the complexity of a problem, you give an algorithm (an upper bound) and a proof that no algorithm can do better (a lower bound). When the two meet, the problem is settled. Sorting by comparisons is settled at Θ(n lg n): merge sort supplies the O, and the decision-tree argument of Chapter 8 supplies the Ω.
O may or may not be tight: 2n² = O(n²) is tight, while 2n = O(n²) is not. Little-oh is the notation for an upper bound that is definitely not tight.
o(g(n)) = { f(n) : for ANY positive constant c > 0, there exists
a constant n₀ > 0 such that 0 ≤ f(n) < c·g(n)
for all n ≥ n₀ }Compare the quantifiers carefully, because that single change is the entire difference:
Quantifier on c | Meaning | Limit form | |
|---|---|---|---|
f = O(g) | There exists some c | f grows no faster than g | lim f/g < ∞ |
f = o(g) | For every c, however small | f becomes insignificant relative to g | lim f/g = 0 |
f = Ω(g) | There exists some c | f grows at least as fast as g | lim f/g > 0 |
f = ω(g) | For every c, however large | f dwarfs g | lim f/g = ∞ |
The limit characterisations on the right are usually the fastest way to settle a question in practice, and CLRS gives them explicitly for o and ω. Examples:
2n = o(n²) // yes: 2n/n² = 2/n → 0
2n² ≠ o(n²) // no: 2n²/n² = 2, not 0
n²/2 = ω(n) // yes: (n²/2)/n = n/2 → ∞
n²/2 ≠ ω(n²) // no: ratio is ½, not ∞
lg n = o(n) // logs lose to any positive power
n¹⁰⁰ = o(2ⁿ) // polynomials lose to exponentialsThe chapter draws the analogy that makes all five easy to remember:
| Notation | Behaves like |
|---|---|
f(n) = O(g(n)) | a ≤ b |
f(n) = Ω(g(n)) | a ≥ b |
f(n) = Θ(g(n)) | a = b |
f(n) = o(g(n)) | a < b |
f(n) = ω(g(n)) | a > b |
Since Θ(g(n)) is a set, the honest statement is f(n) ∈ Θ(g(n)). Everybody writes f(n) = Θ(g(n)) instead. CLRS keeps the equals sign and explains what it means in each position, because the convention is genuinely useful once you know how to read it.
| Where the notation appears | What it means | Example |
|---|---|---|
| Alone on the right | Set membership | n² + n = Θ(n²) means n² + n is a member of that set |
| Inside a formula | Stands for some anonymous function in that set | 2n² + Θ(n) means 2n² + h(n) for some h(n) ∈ Θ(n) |
On the left of = |
“For any choice on the left, there is a choice on the right making it true” | 2n² + Θ(n) = Θ(n²) |
That third row is the one worth pausing on. The equation 2n² + Θ(n) = Θ(n²) asserts: no matter which function h(n) ∈ Θ(n) you pick, 2n² + h(n) lands in Θ(n²). Read that way, chains of such equations compose, which is what lets you write a derivation like this and have each step mean something:
T(n) = 2T(n/2) + Θ(n)
= 2·Θ((n/2) lg(n/2)) + Θ(n)
= Θ(n lg n)n = O(n²) is true; O(n²) = n is meaningless. The equals sign here reads left to right only. This is the price of the convenient notation, and it is why some authors insist on ∈. Read = as “is”, in the sense of “a bee is an insect” — true, but not reversible.One more convention: when asymptotic notation appears in an expression with more than one variable, such as O(m + n) for a graph algorithm, the constants must work uniformly for all sufficiently large values of every variable. CLRS spells this out because it is easy to write a bound that quietly holds only when one parameter dominates.
The notations obey the algebraic properties you would expect from the ≤, ≥, =, <, > analogy.
| Property | Statement | Holds for |
|---|---|---|
| Transitivity | f = Θ(g) and g = Θ(h) imply f = Θ(h) | All five |
| Reflexivity | f(n) = Θ(f(n)) | Θ, O, Ω — not o or ω |
| Symmetry | f = Θ(g) if and only if g = Θ(f) | Θ only |
| Transpose symmetry | f = O(g) if and only if g = Ω(f); likewise f = o(g) iff g = ω(f) | O/Ω and o/ω |
a < b, a = b, a > b holds. For functions, two functions may be incomparable — neither is O of the other. The book’s example is n and n¹⁺ˢᵢⁿⁿ, which oscillates between n⁰ and n² and so is never trapped either way. Real running times are almost never like this, but it means you cannot assume two growth rates are comparable; you have to check.The 4th edition is careful about a slippage that causes real confusion, and it is worth getting straight because it explains statements that otherwise look contradictory.
A running time is not always a single function of n. For a given n, insertion sort takes different amounts of time on different inputs of that size, so “the running time of insertion sort” is a range of values for each n, not one value. That is why we talk about best case, worst case, and average case: each of those is a single function, and asymptotic notation applies to those cleanly.
When we apply the notation directly to the running time itself, this is the convention:
| Statement | Means |
|---|---|
The running time is O(f(n)) | There is a function in O(f(n)) that upper-bounds the running time on every input of size n |
The running time is Ω(f(n)) | There is a function in Ω(f(n)) that lower-bounds the running time on every input of size n |
The running time is Θ(f(n)) | Both of the above, so the running time is pinned regardless of input |
This resolves the apparent paradox in Chapter 2. All of the following are simultaneously true of insertion sort, and each says something different:
worst-case running time = Θ(n²) // reverse-sorted input
best-case running time = Θ(n) // already-sorted input
running time = O(n²) // true on EVERY input
running time = Ω(n) // true on EVERY input
running time ≠ Θ(n²) // false: sorted input is faster
running time ≠ Θ(n) // false: reversed input is slowerMerge sort, by contrast, genuinely has running time Θ(n lg n) without qualification, because it does the same amount of work on every input of a given size. That insensitivity to input is a real property, and it is one of merge sort’s selling points.
Section 3.3 is a reference section. You do not read it end to end; you come back to it. These are the parts that get used.
f is monotonically increasing if m ≤ n implies f(m) ≤ f(n); strictly increasing if m < n implies f(m) < f(n).⌊x⌋ is the greatest integer ≤ x; ⌈x⌉ is the least integer ≥ x. Both are monotonically increasing.x - 1 < ⌊x⌋ ≤ x ≤ ⌈x⌉ < x + 1, and ⌈n/2⌉ + ⌊n/2⌋ = n for any integer n.That last identity is why merge sort can split into ⌈n/2⌉ and ⌊n/2⌋ and still cover the array exactly. Chapter 4 shows that dropping the floors and ceilings from a recurrence does not change its asymptotic solution, which is why nobody carries them around.
CLRS notation, and it is not the notation from your calculus course:
| Written | Means |
|---|---|
lg n | log₂ n — binary logarithm. The default in this book. |
ln n | logᵉ n — natural logarithm |
lgᵏ n | (lg n)ᵏ — exponentiation of the logarithm |
lg lg n | lg(lg n) — composition, which grows extremely slowly |
logᵀ n = logᴸ n / logᴸ a. Since asymptotic notation discards constant factors, Θ(lg n) = Θ(ln n) = Θ(log₁₀ n). The base does matter inside an exponent, though: 2ⁿ and 3ⁿ are not asymptotically equal.The identities that come up:
a = blog_b a logᴸ(ab) = logᴸ a + logᴸ b
logᴸ(aⁿ) = n logᴸ a logᴸ(a/b) = logᴸ a - logᴸ b
alog_b c = clog_b a lg(n!) = Θ(n lg n)a > 1 and b, nᵇ/aⁿ → 0, so nᵇ = o(aⁿ). This is the single most useful comparison in the chapter.eˣ ≥ 1 + x for all x, with equality only at x = 0. Used constantly to bound probabilities in Chapter 5 and beyond.n! = √(2πn) (n/e)ⁿ (1 + Θ(1/n)). The consequences you actually use are n! = o(nⁿ), n! = ω(2ⁿ), and lg(n!) = Θ(n lg n) — the last one is what makes the comparison-sort lower bound in Chapter 8 come out to n lg n.f⁽ⁱ⁾(n) means f applied i times to n. The iterated logarithm counts how many times you must apply lg before the result drops to 1 or below:
lg* n = min { i ≥ 0 : lg(i) n ≤ 1 }n | 2 | 4 | 16 | 65536 | 2⁶⁵⁵³⁶ |
|---|---|---|---|---|---|
lg* n | 1 | 2 | 3 | 4 | 5 |
The number of atoms in the observable universe is far below 2⁶⁵⁵³⁶, so for every input you will ever process, lg* n ≤ 5. It is effectively a constant, and it shows up as the bound for disjoint-set operations in Chapter 19.
F₀ = 0, F₁ = 1, Fᵢ = Fᵢ₋₁ + Fᵢ₋₂. They grow exponentially: Fᵢ = φᵢ/√5 rounded to the nearest integer, where φ = (1 + √5)/2 ≈ 1.618 is the golden ratio. The point for algorithms is that Fibonacci numbers grow exponentially, which is why the naive recursive Fibonacci is exponential-time and why the sequence appears in the analysis of worst-case inputs.
Everything above collapses into one ordering worth memorising. Each entry is o of the next.
| Growth | Name | Typical source | n = 10⁶ means roughly |
|---|---|---|---|
Θ(1) | constant | Array index, hash lookup | 1 step |
Θ(lg* n) | iterated log | Disjoint sets (Ch 19) | 4 steps |
Θ(lg n) | logarithmic | Binary search, balanced tree | 20 steps |
Θ(√n) | root | Trial division to √n | 1,000 steps |
Θ(n) | linear | One scan of the input | 10⁶ steps |
Θ(n lg n) | linearithmic | Merge sort, heapsort | 2 × 10⁷ steps |
Θ(n²) | quadratic | Insertion sort, all pairs | 10¹² steps — minutes to hours |
Θ(n³) | cubic | Floyd-Warshall, naive matrix multiply | 10¹⁸ steps — not happening |
Θ(2ⁿ) | exponential | All subsets | hopeless past n ≈ 40 |
Θ(n!) | factorial | All permutations | hopeless past n ≈ 12 |
lgᵇ n = o(nᵉ) for any b and any a > 0), polynomials beat exponentials’ inverses (nᵇ = o(aⁿ) for any a > 1), and factorials beat exponentials (2ⁿ = o(n!)).Θ, O, and Ω are sets of functions, defined by “there exist constants c and n₀ such that the inequality holds for all n ≥ n₀”.Θ is tight (both sides), O is an upper bound, Ω is a lower bound. Theorem 3.1: Θ is exactly O and Ω together, and that is the standard proof strategy.o and ω change the quantifier from “there exists c” to “for all c”, giving strict bounds. In limit form, f/g → 0 and f/g → ∞.O is ≤, Ω is ≥, Θ is =, o is <, ω is >. Trichotomy fails — two functions can be incomparable.= in f = O(g) means membership, and it reads left to right only. Inside a formula, the notation stands for an anonymous function of that class.O(n²)” means every input of size n is bounded. Insertion sort’s running time is O(n²) and Ω(n) but is Θ of neither; only its per-case functions are.lg means log₂. Bases only matter inside exponents. lg(n!) = Θ(n lg n) from Stirling, which drives the Chapter 8 lower bound.1 ≺ lg* n ≺ lg n ≺ √n ≺ n ≺ n lg n ≺ n² ≺ n³ ≺ 2ⁿ ≺ n!.Chapter 4 puts the notation to work on recurrences. The T(n) = 2T(n/2) + Θ(n) from merge sort gets solved three different ways — substitution, recursion trees, and the master method — and the master theorem in particular becomes a lookup table you will use for the rest of the book.