Asymptotic notation

A cost of 3n² + 10n + 50 grows like n², but what does “like” mean exactly? Watch two copies of n² close round it.

Bounds that hold from some point on

Time and space complexity gave big-O with a constant and a starting point. This lesson states it exactly and adds its two partners. All three compare a cost f(n) with a simpler function g(n), such as n² or n log n, and all three care only about large n. Costs are counts of steps or bytes, so f and g here are never negative.

The clip shows the idea. Near n = 0 the cost is above 4n², and that does not matter: the claim is about what happens from some point on. From n₀ = 14 the cost never leaves the band between 3n² and 4n² again. Once the constants and n₀ are chosen, the bound has to hold for every larger n, with no exceptions.

The definitions

Big O, an upper bound. f(n) = O(g(n)) when there are constants c > 0 and n₀ such that

Big Omega, a lower bound. f(n) = Ω(g(n)) when there are constants c > 0 and n₀ such that

Big Theta, both. f(n) = Θ(g(n)) when there are constants c₁ > 0, c₂ > 0 and n₀ such that

So f = Θ(g) exactly when f = O(g) and f = Ω(g): take the larger of the two starting points. The ”=” is a convention, read as “is”: O(g) is the set of all functions that g bounds from above, and f = O(g) says f is one of them. It is not an equation. n = O(n²) is true, and n² = O(n) is false.

An O bound alone says nothing about how close it is. n is O(n), and also O(n²) and O(2ⁿ). That is why “this costs O(n)” does not mean “this costs about n steps”: it means “no more than a constant times n, for large n”.

Little o and little ω are the strict versions. f(n) = o(g(n)) when for every c > 0, however small, there is an n₀ with f(n) < c·g(n) for every n ≥ n₀: f becomes a vanishing fraction of g. For g positive, that is the same as f(n)/g(n) → 0. Likewise f(n) = ω(g(n)) when for every c > 0 there is an n₀ with f(n) > c·g(n) for every n ≥ n₀, the same as f(n)/g(n) → ∞. So n = o(n²) and n² = ω(n), but n is not o(n).

Comparing by the ratio

Finding constants by hand is often slower than looking at the ratio. If f(n)/g(n) tends to a limit L as n grows:

Why the first row holds: if the ratio tends to L > 0, then from some n₀ on it stays between L/2 and 2L, which is Θ with c₁ = L/2 and c₂ = 2L. For the cost in the clip, (3n² + 10n + 50)/n² = 3 + 10/n + 50/n², which tends to 3, so the cost is Θ(n²).

The test works only when the limit exists. A cost that is n steps for even n and 2n steps for odd n has a ratio to n that jumps between 1 and 2 forever, so it has no limit, yet the cost is Θ(n) with c₁ = 1 and c₂ = 2. Then the definitions decide.

Logarithms and exponentials

The base of a logarithm does not matter inside O. For any bases a, b > 1,

and $1/\log_b a$ is a constant. So log₂ n = Θ(log₁₀ n), and costs are written O(log n) with no base. The base does matter in an exponent: $2^{\log_2 n} = n$, but $2^{\log_4 n} = \sqrt n$.

Any polynomial is beaten by any exponential. For any constants d > 0 and c > 1, $n^d = o(c^n)$: the ratio $n^d / c^n$ tends to 0. In the same way, any power of log n is beaten by any positive power of n: $(\log n)^k = o(n^\varepsilon)$ for every k > 0 and ε > 0.

Cases are not bounds

Worst case, best case and average case say which cost is meant: the most steps over all inputs of size n, the fewest, or the mean over some distribution of inputs. O, Ω and Θ then say how that cost grows. The two choices are separate. Insertion sort takes Θ(n²) steps in the worst case, on reversed input, and Θ(n) in the best case, on sorted input. On every input of size n its cost lies between a constant times n and a constant times n², so it runs in O(n²) and in Ω(n), but no one Θ describes every input. “O is the worst case and Ω the best” mixes the two choices up: a worst case has its own O, Ω and Θ.

Amortised cost, from Dynamic arrays, is a bound on the average cost per operation over a whole sequence of operations, one that holds for every sequence. A push onto a doubling array is O(1) amortised: one push can copy the whole array, but n pushes never cost more than a constant times n in all.

Worked example

Finding the constants. Take f(n) = 3n² + 10n + 50 and g(n) = n². For the upper bound with c = 4,

for n ≥ 0. So c₂ = 4 and n₀ = 14 work: at n = 13, 4n² = 676 < 687 = f(13), and at n = 14, 784 ≥ 778 = f(14). For the lower bound, 3n² ≤ f(n) for every n ≥ 0, so c₁ = 3. Hence f = Θ(n²). Other constants work too: for n ≥ 1, 10n ≤ 10n² and 50 ≤ 50n², so f(n) ≤ 63n² with n₀ = 1. A larger c buys a smaller n₀; the definition asks only that some pair exists.

Changing the base. log₂ n = log₁₀ n / log₁₀ 2 ≈ 3.32 log₁₀ n, a constant factor of 3.32.

A bound says nothing about where it starts. n¹⁰⁰ against 1.01ⁿ: the ratio tends to 0, so n¹⁰⁰ = O(1.01ⁿ), and even o(1.01ⁿ). Yet n¹⁰⁰ is the larger for every n from 2 to 117,308, and 1.01ⁿ takes over for good only from n = 117,309: at n = 1,000 it is 10³⁰⁰ against 1.01¹⁰⁰⁰ ≈ 21,000.

Constants in exponents are not constant factors. 2ⁿ⁺¹ = 2 · 2ⁿ, so 2ⁿ⁺¹ = Θ(2ⁿ) with c = 2. But 2²ⁿ = 4ⁿ, and 4ⁿ / 2ⁿ = 2ⁿ grows without bound, so 4ⁿ is not O(2ⁿ).

Two checks. Is 5n + 3 = O(n²)? (Yes: 5n + 3 ≤ 8n² for n ≥ 1; but not Θ(n²), since (5n + 3)/n² tends to 0.) Is n log n = $O(n^{1.5})$? (Yes: the ratio is $\log n / \sqrt n$, which tends to 0.)

Where it’s used

Every cost claim in this course, and in library documentation: a sort in O(n log n), a hash table lookup in O(1) on average, a binary search in O(log n).

Choosing between algorithms before writing them, keeping in mind that a smaller bound wins only for large enough n: an O(n log n) method with a large constant can lose to an O(n²) one on small inputs.

Reference card