Chapter IV · Limits of functions of a positive integral variable

The symbols OO, oo and ∼\sim

§89 30 min

A compact language for comparing how fast two sequences grow or shrink, its rules, and its one-way equals sign.

Why this matters

Often we do not need to know a sequence exactly, only how big it is compared with something simple. Is 100n2+1000n100n^2 + 1000n “about n2n^2”? Is sin⁡n\sin n “small compared with nn”? §89 introduces three symbols that make such statements precise and short: OO (“at most of the order of”), oo (“of smaller order than”) and ∼\sim (“of the same order, with a definite ratio”). Hardy says he will not use them until later chapters; they are now part of the everyday language of analysis, number theory and computer science.

The idea

All three symbols are statements about the ratio f(n)/ϕ(n)f(n)/\phi(n), where ϕ(n)\phi(n) is some simple comparison sequence such as 11, nn or n2n^2:

  • f=O(ϕ)f = O(\phi): the ratio stays bounded (in absolute value).
  • f=o(ϕ)f = o(\phi): the ratio tends to 00.
  • f∼lϕf \sim l\phi: the ratio tends to a limit l≠0l \neq 0.

So a single picture, the graph of the ratio, decides all three. Over a long range of nn this is best drawn with nn on a logarithmic scale.

Explore The ratio race

Try this. Start with f=100n2+1000nf = 100n^2 + 1000n and compare it in turn with ϕ=n\phi = n, n2n^2 and n3n^3. Then compare sin⁡n\sin n with 11 and with n\sqrt n, and (2+(−1)n) n(2 + (-1)^n)\,n with nn.

f(n)ϕ(n)=100n2+1000nn2\frac{f(n)}{\phi(n)} = \frac{100n^2 + 1000n}{n^2}
n (log scale)f/φ
  • f(n)/φ(n)
  • ±K with K = 1100, the largest |f/φ| for n ≤ 10⁶
  • limit of the ratio: 100
At n=106n = 10^6 the ratio is 100. f=O(ϕ)f = O(\phi) ✓ · f=o(ϕ)f = o(\phi) ✗ · f∼lϕf \sim l\phi ✓ with l=100l = 100. The ratio settles to 100: f and φ grow at the same rate, up to that factor.
What to notice

Against n2n^2 the ratio settles at 100100: same order with a definite ratio, f∼100n2f \sim 100n^2. Against n3n^3 it dies away (oo), and against nn it runs off the top (not even OO). The early terms are irrelevant: the ratio starts at 11001100 but only its eventual behaviour counts. sin⁡n\sin n and (2+(−1)n)n(2 + (-1)^n)n show the gap between OO and ∼\sim: the ratio stays bounded but never settles.

Precise statements

Throughout, ϕ(n)\phi(n) is positive and monotone (it increases or decreases steadily), so that it tends to 00, to a positive limit, or to +∞+\infty. In practice it is something like 1/n1/n, 11, nn or n2n^2.

Definition OO, oo and ∼\sim Hardy: §89 (i)–(iii)

Let f(n)f(n) be defined for all sufficiently large nn.

  • (i) If there is a constant KK with ∣f(n)∣≤Kϕ(n)|f(n)| \le K\phi(n) for all sufficiently large nn, we write f=O(ϕ)f = O(\phi).
  • (ii) If f(n)/ϕ(n)→0f(n)/\phi(n) \to 0, we write f=o(ϕ)f = o(\phi).
  • (iii) If f(n)/ϕ(n)→lf(n)/\phi(n) \to l with l≠0l \neq 0, we write f∼lϕf \sim l\phi.

In particular f=O(1)f = O(1) means that ff is bounded, and f=o(1)f = o(1) means that f→0f \to 0.

Hardy’s own examples:

n=O(n2),100n2+1000n=O(n2),sin⁡nθπ=O(1);n = O(n^2), \quad 100n^2 + 1000n = O(n^2), \quad \sin n\theta\pi = O(1); n=o(n2),100n2+1000n=o(n3),sin⁡nθπ=o(n);n = o(n^2), \quad 100n^2 + 1000n = o(n^3), \quad \sin n\theta\pi = o(n); n+1∼n,100n2+1000n∼100n2,n+sin⁡nθπ∼n;n + 1 \sim n, \quad 100n^2 + 1000n \sim 100n^2, \quad n + \sin n\theta\pi \sim n;

and, for polynomials with a0≠0a_0 \ne 0, b0≠0b_0 \ne 0,

a0np+a1np−1+⋯+apb0nq+b1nq−1+⋯+bq∼a0b0 np−q.\frac{a_0 n^p + a_1 n^{p-1} + \cdots + a_p}{b_0 n^q + b_1 n^{q-1} + \cdots + b_q} \sim \frac{a_0}{b_0}\, n^{p - q}.

Note that f=O(ϕ)f = O(\phi) does not say ff is as large as ϕ\phi, only that it is not larger in order: n=O(n2)n = O(n^2) is true. The symbol O(ϕ)O(\phi) on its own stands for “some unspecified ff with f=O(ϕ)f = O(\phi)”, which lets us write chains such as O(1)+O(1)=O(1)O(1) + O(1) = O(1).

Theorem Rules for the symbols Hardy: §89
  • (1) O(ϕ)+O(ψ)=O(ϕ+ψ)O(\phi) + O(\psi) = O(\phi + \psi).
  • (2) O(ϕ) O(ψ)=O(ϕψ)O(\phi)\,O(\psi) = O(\phi\psi).
  • (3) O(ϕ) o(ψ)=o(ϕψ)O(\phi)\,o(\psi) = o(\phi\psi).
  • (4) If f∼ϕf \sim \phi, then f+o(ϕ)∼ϕf + o(\phi) \sim \phi.
  • (5) o(ϕ)=O(ϕ)o(\phi) = O(\phi), but not O(ϕ)=o(ϕ)O(\phi) = o(\phi): these “equations” are read from left to right only.

Proofs

Proof The rules (1)–(3)
Strategy

Translate each symbol back into an inequality or a limit about a ratio, combine, and translate back.

(1): bounded plus bounded

If ∣f∣≤Kϕ|f| \le K\phi and ∣g∣≤Lψ|g| \le L\psi for large nn, then ∣f+g∣≤∣f∣+∣g∣≤Kϕ+Lψ≤max⁡(K,L)(ϕ+ψ)|f + g| \le |f| + |g| \le K\phi + L\psi \le \max(K, L)(\phi + \psi).

(2): bounded times bounded

With the same ff, gg: ∣fg∣≤KL ϕψ|fg| \le KL\,\phi\psi.

(3): bounded times null

If ∣f∣≤Kϕ|f| \le K\phi and g/ψ→0g/\psi \to 0, then ∣fgϕψ∣≤K∣gψ∣→0\left|\dfrac{fg}{\phi\psi}\right| \le K\left|\dfrac{g}{\psi}\right| \to 0, so fg=o(ϕψ)fg = o(\phi\psi).

Proof (4) and (5)
Strategy

Again work with ratios: adding something whose ratio to ϕ\phi tends to 00 cannot change a limiting ratio; and a ratio that tends to 00 is bounded, but not conversely.

(4)

If f/ϕ→1f/\phi \to 1 and g/ϕ→0g/\phi \to 0, then (f+g)/ϕ=f/ϕ+g/ϕ→1+0=1(f + g)/\phi = f/\phi + g/\phi \to 1 + 0 = 1. (The same argument gives f+o(ϕ)∼lϕf + o(\phi) \sim l\phi whenever f∼lϕf \sim l\phi.)

(5): oo implies OO

If f/ϕ→0f/\phi \to 0, then ∣f/ϕ∣<1|f/\phi| < 1 for all large nn, so ∣f∣≤1⋅ϕ|f| \le 1 \cdot \phi for large nn: f=O(ϕ)f = O(\phi).

(5): OO does not imply oo

f(n)=1f(n) = 1 is O(1)O(1) but not o(1)o(1), since it does not tend to 00. So “O(1)=o(1)O(1) = o(1)” is false although “o(1)=O(1)o(1) = O(1)” is true: the equals sign here means “is of the kind”, not equality.

Proof The ratio of two polynomials
Strategy

Divide the top by npn^p and the bottom by nqn^q: every term except the leading one gets a negative power of nn and tends to 00.

Rewrite the ratio

a0np+⋯+apb0nq+⋯+bq/np−q=a0+a1/n+⋯+ap/npb0+b1/n+⋯+bq/nq.\frac{a_0 n^p + \cdots + a_p}{b_0 n^q + \cdots + b_q} \Big/ n^{p-q} = \frac{a_0 + a_1/n + \cdots + a_p/n^p}{b_0 + b_1/n + \cdots + b_q/n^q}.

Take limits

Each ak/nka_k/n^k and bk/nkb_k/n^k with k≥1k \ge 1 tends to 00, so the numerator tends to a0a_0 and the denominator to b0≠0b_0 \neq 0. By the quotient theorem the ratio tends to a0/b0≠0a_0/b_0 \ne 0, which is the definition of ∼a0b0 np−q\sim \tfrac{a_0}{b_0}\, n^{p-q}. (The denominator polynomial vanishes for at most finitely many nn, and the definitions only concern large nn.)

Worked examples and exercises

Exercise ●○○ Hardy: §89

Decide which of OO, oo, ∼\sim hold, and with which constant: (a) f=3n2−7n+2f = 3n^2 - 7n + 2 against n2n^2; (b) f=nsin⁡nf = n\sin n against nn; (c) f=n2+1f = \sqrt{n^2 + 1} against nn; (d) f=1/(n2+1)f = 1/(n^2 + 1) against 1/n1/n.

Hint
Compute f/ϕf/\phi in each case, and ask whether it is bounded, tends to 00, or tends to a non-zero limit.

Solution

(a) f/n2=3−7/n+2/n2→3f/n^2 = 3 - 7/n + 2/n^2 \to 3: so f∼3n2f \sim 3n^2, f=O(n2)f = O(n^2), not o(n2)o(n^2).

(b) f/n=sin⁡nf/n = \sin n, bounded but (as one can show) without a limit: f=O(n)f = O(n), neither o(n)o(n) nor ∼ln\sim ln.

(c) f/n=1+1/n2→1f/n = \sqrt{1 + 1/n^2} \to 1: f∼nf \sim n (and O(n)O(n)).

(d) f/(1/n)=n/(n2+1)→0f/(1/n) = n/(n^2 + 1) \to 0: f=o(1/n)f = o(1/n), and in fact f∼1/n2f \sim 1/n^2.

Exercise A sum of bounded terms ●○○ Hardy: §89

Explain and prove the formula ∑r=1nO(1)=O(n)\sum_{r=1}^{n} O(1) = O(n).

Hint
Be careful: the bound must be the same for every term.

Solution

It means: if ∣ur∣≤K|u_r| \le K for every rr (one constant KK for all the terms), then ∣u1+⋯+un∣≤Kn|u_1 + \cdots + u_n| \le Kn, so u1+⋯+un=O(n)u_1 + \cdots + u_n = O(n). The proof is the triangle inequality: ∣u1+⋯+un∣≤∣u1∣+⋯+∣un∣≤nK|u_1 + \cdots + u_n| \le |u_1| + \cdots + |u_n| \le nK. If each term only had its own bound, the statement would fail: ur=ru_r = r is bounded for each fixed rr, yet 1+2+⋯+n∼12n21 + 2 + \cdots + n \sim \tfrac12 n^2.

Exercise ●●○ Hardy: §89

Show that n+1−n∼12n\sqrt{n+1} - \sqrt n \sim \dfrac{1}{2\sqrt n}, and deduce that n+1−n=o(1)\sqrt{n+1} - \sqrt n = o(1).

Hint
Multiply and divide by n+1+n\sqrt{n+1} + \sqrt n.

Solution

n+1−n=1n+1+n\sqrt{n+1} - \sqrt n = \dfrac{1}{\sqrt{n+1} + \sqrt n}. Its ratio to 1/(2n)1/(2\sqrt n) is 2nn+1+n=21+1/n+1→1\dfrac{2\sqrt n}{\sqrt{n+1} + \sqrt n} = \dfrac{2}{\sqrt{1 + 1/n} + 1} \to 1. Hence n+1−n∼12n−1/2\sqrt{n+1} - \sqrt n \sim \tfrac12 n^{-1/2}, and since n−1/2→0n^{-1/2} \to 0, it is o(1)o(1) (indeed =O(n−1/2)= O(n^{-1/2}), so the difference tends to 00 about as fast as 1/n1/\sqrt n).

Exercise ∼\sim is not compatible with subtraction ●●○ Hardy: §89

Show that f∼ϕf \sim \phi and g∼ϕg \sim \phi imply f−g=o(ϕ)f - g = o(\phi), but need not imply f−g∼hf - g \sim h for any simple hh you might guess. Give an example with f∼gf \sim g but f−gf - g not o(1)o(1).

Hint
Take f=n+1f = n + 1, g=ng = n, ϕ=n\phi = n.

Solution

If f/ϕ→1f/\phi \to 1 and g/ϕ→1g/\phi \to 1, then (f−g)/ϕ→0(f - g)/\phi \to 0: so f−g=o(ϕ)f - g = o(\phi). This is all that can be said: with f=n+1f = n + 1, g=ng = n we have f∼g∼nf \sim g \sim n, but f−g=1f - g = 1, which is not o(1)o(1). With f=n+nf = n + \sqrt n and g=ng = n, the difference is n\sqrt n, which tends to infinity. Asymptotic equality says the relative error tends to 00; the absolute error can be anything of smaller order than ϕ\phi.

Check yourself

Check yourself True or false?

O(1)=o(1)O(1) = o(1).

Why

False. Read it as “every bounded sequence tends to 00”, which f(n)=1f(n) = 1 refutes. The other direction, o(1)=O(1)o(1) = O(1), is true: every null sequence is bounded. Equations with OO and oo are read from left to right.

Check yourself Choose one

Which statement about f(n)=100n2+1000nf(n) = 100n^2 + 1000n is false?

Why

f/n2=100+1000/n→100f/n^2 = 100 + 1000/n \to 100, which is not 00, so ff is not o(n2)o(n^2). It is O(n2)O(n^2) (bounded ratio), hence also O(n3)O(n^3) (an OO statement may be generous), and f∼100n2f \sim 100n^2.

Check yourself Enter a number

If f(n)=6n3−n2n+5f(n) = \dfrac{6n^3 - n}{2n + 5} and f∼ln2f \sim l n^2, what is ll?

Why

Leading terms: 6n3/(2n)=3n26n^3/(2n) = 3n^2, so l=6/2=3l = 6/2 = 3. Formally, f/n2=6−1/n22+5/n→3f/n^2 = \dfrac{6 - 1/n^2}{2 + 5/n} \to 3.

Check yourself True or false?

(2+(−1)n) n=O(n)(2 + (-1)^n)\,n = O(n), but there is no ll with (2+(−1)n) n∼ln(2 + (-1)^n)\,n \sim l n.

Why

True. The ratio to nn is 1,3,1,3,…1, 3, 1, 3, \dots: bounded by 33, so O(n)O(n), but it has no limit, so no ∼\sim statement holds. OO only needs a bound; ∼\sim needs a limiting ratio.

Hardy’s language

Summary

Summary
  • f=O(ϕ)f = O(\phi): ∣f/ϕ∣|f/\phi| eventually bounded. f=o(ϕ)f = o(\phi): f/ϕ→0f/\phi \to 0. f∼lϕf \sim l\phi: f/ϕ→l≠0f/\phi \to l \ne 0.
  • O(1)O(1) means bounded, o(1)o(1) means tending to 00. Only the eventual behaviour counts.
  • oo implies OO, not conversely; the equals sign is one-way.
  • Rules: O+O=OO + O = O, O⋅O=OO \cdot O = O, O⋅o=oO \cdot o = o, and adding o(ϕ)o(\phi) does not change f∼ϕf \sim \phi.
  • A ratio of polynomials is ∼\sim (ratio of leading coefficients) × ndifference of degrees\times\, n^{\text{difference of degrees}}.