Lesson · Algorithms and Complexity · Analysis

Big-O, Big-Omega and Big-Theta

f(n) = O(g(n)) asserts the existence of a constant C and a threshold k with f(n) ≤ Cg(n) beyond k. Proving it means producing them; that is the entire content of the definition.

Open the interactive lesson Practice

O(g) f ≤ C·g for n ≥ k upper bound Ω(g) f ≥ C·g for n ≥ k lower bound Θ(g) both tight the proof IS the pair (C, k)

Three relations, one shape

Core ideas

What this lesson establishes

Each of the three is an existence claim, and each is proved by exhibiting the witnesses.

Big-O is an upper bound and may be loose

n = O(n²) is true and uninformative. "Is O(n²)" does not mean "grows like n²".

Θ is the tight statement

Both bounds. It is what should be claimed when the growth is actually known, and the one people usually mean when they say O.

The witnesses are the proof

A C and a k that work. Anything else is a restatement of the claim.

The material

The three notations

Definitions, worked proofs, and the properties that shorten later work.

Definition · Big-O

f(n) = O(g(n)) means there are constants C > 0 and k such that |f(n)| ≤ C|g(n)| for every n ≥ k. The pair (C, k) is a witness.

Definition · Big-Omega and Big-Theta

f(n) = Ω(g(n)) means |f(n)| ≥ C|g(n)| for some C > 0 and all n ≥ k. f(n) = Θ(g(n)) means both, so f and g grow at the same rate.

The = is traditional and misleading: these are set memberships, and O(g) is the class of functions bounded above by a multiple of g. f(n) = O(g(n)) should be read "f is in O(g)", and it is not symmetric.

Proving a bound

Example · 3n² + 5n + 100 = O(n²)

For n ≥ 1 we have n ≤ n² and 1 ≤ n², so 3n² + 5n + 100 ≤ 3n² + 5n² + 100n² = 108n². The witnesses are C = 108 and k = 1. Sharper choices exist — at n ≥ 10, C = 5 works — and any valid pair proves the claim.

Example · n² ≠ O(n)

Suppose n² ≤ Cn for all n ≥ k. Dividing by n gives n ≤ C for all n ≥ k, which is false for n > max(C, k). No pair of witnesses exists.

That is the shape of a disproof: assume witnesses and derive a contradiction. It is a direct proof of a negation, and “Contraposition and Contradiction” in Logic and Proof is the technique.

Useful properties

transitive f = O(g), g = O(h) ⟹ f = O(h) sum f₁ = O(g₁), f₂ = O(g₂) ⟹ f₁+f₂ = O(max(g₁,g₂)) product f₁ = O(g₁), f₂ = O(g₂) ⟹ f₁·f₂ = O(g₁·g₂) constants c·f = O(f) for any constant c > 0 polynomials aₖnᵏ + … + a₀ = Θ(nᵏ) logs log_a n = Θ(log_b n) — the base is a constant factor

The last line is why the base of a logarithm is never written in a complexity class: log₂ n and log₁₀ n differ by the constant factor log₂ 10, which Θ discards.

The sum rule is what makes analysis of straight-line code easy: a sequence of blocks costs the maximum of their costs, not the sum, in asymptotic terms.

The common misuse

"Quicksort is O(n log n)" is a widespread and false statement: quicksort's worst case is Θ(n²). What is true is that its average case is Θ(n log n). Big-O is an upper bound and quoting it without saying which case is being bounded loses the distinction the notation exists to express.

Similarly "at least O(n)" is meaningless — O is already an upper bound — and "Ω" is the word wanted there.

Interactive

Algorithms and growth

Counts from running, not from quoting

Find the witnesses

The lab opens on the body's claim, 3n² + 5n + 100 against n², and finds C = 4, k = 13 — a sharper pair than the body's C = 108, k = 1, and equally a proof; the rows below k are highlighted where the bound fails, which is what k is for. Set f to n² and g to n for the body's disproof: no pair exists, and the lab shows the ratio n²/n running through 10, 100, 1 000 … instead of inventing a constant. That verdict comes from the growth classes, not from a search — a search that stopped at n = 64 would report C = 100, and every finite search has that flaw. Try n log₂ n against n for the same reason.

What to examine

f(n)

g(n)

Input order

Growth policy

a (subproblems)

b (shrink factor)

d (combining cost n^d)

n16

measured—

predicted—

Method

Proving a big-O claim

Bound each term, then collect.

Bound every term by a multiple of g(n)

For n ≥ 1, lower powers are bounded by higher ones. That is usually the whole argument.

Add the coefficients to get C

Any valid C proves the claim. Optimising it is not required and rarely worth the effort.

State the threshold k

The bound need only hold beyond it, which is what lets small-n behaviour be ignored.

To disprove, assume witnesses and derive a contradiction

Divide through by g(n) and show the resulting bound on n is impossible.

Asymptotic notation

Score 0 / 0

Choose the answer you can justify.

Two proofs

One positive, one negative.

CLAIM n² + 2n + 1 = O(n²) for n ≥ 1: 2n ≤ 2n² and 1 ≤ n² so n² + 2n + 1 ≤ n² + 2n² + n² = 4n² WITNESSES C = 4, k = 1. ∎ CLAIM 2ⁿ ≠ O(n¹⁰⁰) Suppose 2ⁿ ≤ C·n¹⁰⁰ for all n ≥ k. Then 2ⁿ / n¹⁰⁰ ≤ C, a bounded quantity. But 2ⁿ / n¹⁰⁰ → ∞, since exponential growth eventually dominates any fixed power. Contradiction. ∎

The first proof produced a specific pair, which is what the definition asks for. The second assumed a pair existed and refuted it. Every big-O argument on this course has one of these two shapes.

Common mistakes

Claiming O where Θ is meantn = O(n²) is true and says almost nothing. If the growth is known, say Θ.

Omitting which case is being boundedWorst, average and best case are different functions. "Quicksort is O(n log n)" is false; "its average case is" is true.

Writing "at least O(n)"O is already an upper bound. The intended word is Ω.

Check your understanding

✓

Finish when you produce witnesses without being asked.

Prove 5n³ + 2n² + n = O(n³) by exhibiting a C and a k (C = 8, k = 1 is one pair), and then prove n³ ≠ O(n²) by contradiction: divide the supposed bound through by n². The two shapes cover almost every claim you will meet.

Note: The notation is due to Bachmann and Landau, from analytic number theory, and Knuth introduced it to algorithm analysis. The abuse of = is his too, and it is now unfixable.