The idea: a bound is a curve that f cannot cross after n₀

"Merge sort is O(n log n)" is a claim about a function: the number of steps f(n) for input size n. It says that some multiple of n log n stays above f once n is big enough. Ω says some multiple stays below, and Θ says f is squeezed between two multiples. The page draws those multiples, c·g(n), as dashed curves, and marks every n on the plot green where the inequality holds and red where it fails.

Three small plots. O: an orange dashed curve c·g(n) crosses above the blue f(n) at n0 and stays above it. Omega: a green dashed curve c·g(n) stays below f(n) from n0 on. Theta: f(n) runs between a green lower curve c1·g(n) and an orange upper curve c2·g(n) from n0 on. The region right of n0 is shaded in each plot.
O caps f from above, Ω props it up from below, Θ does both, and each one only has to work from n₀ on.

The definitions

ClaimMeans: there are constants withLimit test (if f/g has a limit L)
f = O(g)f(n) ≤ c·g(n) for every n ≥ n₀L is finite (0 or a constant)
f = Ω(g)f(n) ≥ c·g(n) for every n ≥ n₀, c > 0L > 0 (a constant or ∞)
f = Θ(g)c₁·g(n) ≤ f(n) ≤ c₂·g(n) for every n ≥ n₀0 < L < ∞
f = o(g)for every c > 0 some n₀ works for f(n) ≤ c·g(n)L = 0
f = ω(g)for every c some n₀ works for f(n) ≥ c·g(n)L = ∞

O is an upper bound, not "exactly": 3n² + 10n + 20 is O(n²), and also O(n³) and O(2ⁿ). Only Θ pins the growth rate down. On the page, O uses c₂ (the upper curve, orange), Ω uses c₁ (the lower curve, green), and Θ uses both.

c and n₀ are the witnesses

To prove a bound you name the two constants. For 3n² + 10n + 20 ≤ 4n² you need n² ≥ 10n + 20, which is true from n = 12 on: f(11) = 493 > 484 = 4·11², but f(12) = 572 ≤ 576. So c = 4, n₀ = 12 is a proof (Demo: 3n²+10n+20 = O(n²), c = 4). A bigger c gives a smaller n₀: with c = 5 it holds from n₀ = 7. With c = 3 no n₀ works, because f is always more than 3n².

For Θ the same function is squeezed: 3n² ≤ f(n) for every n, and f(n) ≤ 4n² from 12 on, so Θ(n²) with c₁ = 3, c₂ = 4, n₀ = 12 (Demo: Θ(n²): squeezed by 3n² and 4n²).

n₀ is there to ignore small inputs. Big constants push it out: 50n + 400 ≤ n² only from n₀ = 58, even though 50n + 400 is the "faster" function (Demo: big constants). And the inequality may flip more than once: n³ ≤ 2ⁿ at n = 1, fails at 2 to 9 (729 > 512 at n = 9), and holds from n₀ = 10 (1,000 ≤ 1,024) for good (Demo: n³ = O(2ⁿ), n₀ = 10).

A plot is not a proof

On the plot (n up to 20) every dot for 3n² + 10n + 20 ≤ 100n is green. But at n = 30, f = 3,020 > 3,000, and from there on it fails for good (Demo: the plot lies). The claim is about every n ≥ n₀, so a finite picture can only refute, never prove. The page decides with the limit of f(n)/g(n): here f/n → ∞, so no c is big enough and f is not O(n). When the limit is a constant L, every c₂ > L works for O and every c₁ < L for Ω. When L equals c exactly, the lower-order terms decide.

Best, worst and average case are not O, Ω, Θ

These are two different questions. A case picks which inputs you count: the worst case is the most steps over all inputs of size n, the best case the fewest, the average case the mean over some distribution. Each case is one function of n. A bound (O, Ω, Θ) then describes how a function grows. You can put any bound on any case.

Insertion sort comparisons from n = 1 to 20: a shaded band between the best case n − 1 (sorted input) and the worst case n(n − 1)/2 (reversed input). An orange dashed n² curve stays above the whole band and a green dashed n/2 curve stays below it. A green dotted n²/2 curve runs just above the worst case, far above the best case, so it is not a lower bound.
Every input of size n costs somewhere in the band: n² caps all of it and n/2 props all of it, but no single c·n² does both.

Insertion sort makes n − 1 comparisons on sorted input and n(n − 1)/2 on reversed input. So:

StatementTrue?Why
worst case is Θ(n²)✓n(n − 1)/2 over n² → ½
best case is Θ(n)✓(n − 1)/n → 1
insertion sort is O(n²)✓n² is above the worst case, so above every input
insertion sort is Ω(n)✓n/2 is below the best case from n = 2
insertion sort is Θ(n²)✗sorted input: (n − 1)/n² → 0, no c₁ fits under it
insertion sort is O(n)✗reversed input: n(n − 1)/2 over n → ∞

So "the worst case is O(n²)" and "the best case is Ω(n)" are both fine; "O means worst case, Ω means best case" is a common mix-up (Demo: insertion sort: O(n²), Ω(n), not Θ). Merge sort, by contrast, is Θ(n log n) on every input, so its running time has one tight bound.

Common mistakes

  • Reading "=" as equality: O(n) = O(n²) is true, O(n²) = O(n) is not. It means "is in the set".
  • Saying O when Θ is meant: "binary search is O(n)" is true and useless; it is Θ(log n) in the worst case.
  • Forgetting the constants: O hides them, so an O(n) algorithm with a big constant loses to an O(n²) one on small inputs. See the Big-O Growth Race for where 100·n and n² cross.

To compare growth rates side by side on real operation counts, see Big-O Growth Race. To get Θ bounds for divide-and-conquer recurrences, see the Master Theorem, and for the sorts behind the table see Comparison Sorting.

What the page leaves out

The page tests a bound only for c from a short list and decides "for every n" with the limit of f/g, which exists for all its functions. Functions whose ratio swings forever (like n·(1 + sin n)) need limsup and liminf instead. Little-o and little-ω are in the table but not drawn. Average-case analysis, amortized bounds, and bounds in more than one variable (O(V + E)) are not shown.