Often we do not need to know a sequence exactly, only how big it is compared with something simple. Is 100n2+1000n “about n2”? Is sinn “small compared with n”? §89 introduces three symbols that make such statements precise and short: O (“at most of the order of”), o (“of smaller order than”) and ∼ (“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 ratiof(n)/ϕ(n), where ϕ(n) is some simple comparison sequence such as 1, n or n2:
f=O(ϕ): the ratio stays bounded (in absolute value).
f=o(ϕ): the ratio tends to 0.
f∼lϕ: the ratio tends to a limit l=0.
So a single picture, the graph of the ratio, decides all three. Over a long range of n this is best drawn with n on a logarithmic scale.
ExploreThe ratio race
Try this.Start with f=100n2+1000n and compare it in turn with ϕ=n, n2 and n3. Then compare sinn with 1 and with n, and (2+(−1)n)n with n.
ϕ(n)f(n)=n2100n2+1000n
n (log scale)f/φ
f(n)/φ(n)
±K with K = 1100, the largest |f/φ| for n ≤ 10⁶
limit of the ratio: 100
At n=106 the ratio is 100. f=O(ϕ) ✓ · f=o(ϕ) ✗ · f∼lϕ ✓ with l=100. The ratio settles to 100: f and φ grow at the same rate, up to that factor.
What to notice
Against n2 the ratio settles at 100: same order with a definite ratio, f∼100n2. Against n3 it dies away (o), and against n it runs off the top (not even O). The early terms are irrelevant: the ratio starts at 1100 but only its eventual behaviour counts. sinn and (2+(−1)n)n show the gap between O and ∼: the ratio stays bounded but never settles.
Precise statements
Throughout, ϕ(n) is positive and monotone (it increases or decreases steadily), so that it tends to 0, to a positive limit, or to +∞. In practice it is something like 1/n, 1, n or n2.
DefinitionO, o and ∼Hardy: §89 (i)–(iii)
Let f(n) be defined for all sufficiently large n.
(i) If there is a constant K with ∣f(n)∣≤Kϕ(n) for all sufficiently large n, we write f=O(ϕ).
(ii) If f(n)/ϕ(n)→0, we write f=o(ϕ).
(iii) If f(n)/ϕ(n)→l with l=0, we write f∼lϕ.
In particular f=O(1) means that f is bounded, and f=o(1) means that f→0.
Note that f=O(ϕ) does not say f is as large as ϕ, only that it is not larger in order: n=O(n2) is true. The symbol O(ϕ) on its own stands for “some unspecified f with f=O(ϕ)”, which lets us write chains such as O(1)+O(1)=O(1).
TheoremRules for the symbolsHardy: §89
(1) O(ϕ)+O(ψ)=O(ϕ+ψ).
(2) O(ϕ)O(ψ)=O(ϕψ).
(3) O(ϕ)o(ψ)=o(ϕψ).
(4) If f∼ϕ, then f+o(ϕ)∼ϕ.
(5) o(ϕ)=O(ϕ), but not O(ϕ)=o(ϕ): these “equations” are read from left to right only.
Proofs
ProofThe 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ϕ and ∣g∣≤Lψ for large n, then ∣f+g∣≤∣f∣+∣g∣≤Kϕ+Lψ≤max(K,L)(ϕ+ψ).
(2): bounded times bounded
With the same f, g: ∣fg∣≤KLϕψ.
(3): bounded times null
If ∣f∣≤Kϕ and g/ψ→0, then ϕψfg≤Kψg→0, so fg=o(ϕψ).
∎
Proof(4) and (5)
Strategy
Again work with ratios: adding something whose ratio to ϕ tends to 0 cannot change a limiting ratio; and a ratio that tends to 0 is bounded, but not conversely.
(4)
If f/ϕ→1 and g/ϕ→0, then (f+g)/ϕ=f/ϕ+g/ϕ→1+0=1. (The same argument gives f+o(ϕ)∼lϕ whenever f∼lϕ.)
(5): o implies O
If f/ϕ→0, then ∣f/ϕ∣<1 for all large n, so ∣f∣≤1⋅ϕ for large n: f=O(ϕ).
(5): O does not imply o
f(n)=1 is O(1) but not o(1), since it does not tend to 0. So “O(1)=o(1)” is false although “o(1)=O(1)” is true: the equals sign here means “is of the kind”, not equality.
∎
ProofThe ratio of two polynomials
Strategy
Divide the top by np and the bottom by nq: every term except the leading one gets a negative power of n and tends to 0.
Each ak/nk and bk/nk with k≥1 tends to 0, so the numerator tends to a0 and the denominator to b0=0. By the quotient theorem the ratio tends to a0/b0=0, which is the definition of ∼b0a0np−q. (The denominator polynomial vanishes for at most finitely many n, and the definitions only concern large n.)
∎
Worked examples and exercises
Exercise●○○Hardy: §89
Decide which of O, o, ∼ hold, and with which constant: (a) f=3n2−7n+2 against n2; (b) f=nsinn against n; (c) f=n2+1 against n; (d) f=1/(n2+1) against 1/n.
Hint
Compute f/ϕ in each case, and ask whether it is bounded, tends to 0, or tends to a non-zero limit.
Solution
(a) f/n2=3−7/n+2/n2→3: so f∼3n2, f=O(n2), not o(n2).
(b) f/n=sinn, bounded but (as one can show) without a limit: f=O(n), neither o(n) nor ∼ln.
(c) f/n=1+1/n2→1: f∼n (and O(n)).
(d) f/(1/n)=n/(n2+1)→0: f=o(1/n), and in fact f∼1/n2.
ExerciseA sum of bounded terms●○○Hardy: §89
Explain and prove the formula ∑r=1nO(1)=O(n).
Hint
Be careful: the bound must be the same for every term.
Solution
It means: if ∣ur∣≤K for every r (one constant K for all the terms), then ∣u1+⋯+un∣≤Kn, so u1+⋯+un=O(n). The proof is the triangle inequality: ∣u1+⋯+un∣≤∣u1∣+⋯+∣un∣≤nK. If each term only had its own bound, the statement would fail: ur=r is bounded for each fixed r, yet 1+2+⋯+n∼21n2.
Exercise●●○Hardy: §89
Show that n+1−n∼2n1, and deduce that n+1−n=o(1).
Hint
Multiply and divide by n+1+n.
Solution
n+1−n=n+1+n1. Its ratio to 1/(2n) is n+1+n2n=1+1/n+12→1. Hence n+1−n∼21n−1/2, and since n−1/2→0, it is o(1) (indeed =O(n−1/2), so the difference tends to 0 about as fast as 1/n).
Exercise∼ is not compatible with subtraction●●○Hardy: §89
Show that f∼ϕ and g∼ϕ imply f−g=o(ϕ), but need not imply f−g∼h for any simple h you might guess. Give an example with f∼g but f−g not o(1).
Hint
Take f=n+1, g=n, ϕ=n.
Solution
If f/ϕ→1 and g/ϕ→1, then (f−g)/ϕ→0: so f−g=o(ϕ). This is all that can be said: with f=n+1, g=n we have f∼g∼n, but f−g=1, which is not o(1). With f=n+n and g=n, the difference is n, which tends to infinity. Asymptotic equality says the relative error tends to 0; the absolute error can be anything of smaller order than ϕ.
Check yourself
Check yourselfTrue or false?
O(1)=o(1).
Why
False. Read it as “every bounded sequence tends to 0”, which f(n)=1 refutes. The other direction, o(1)=O(1), is true: every null sequence is bounded. Equations with O and o are read from left to right.
Check yourselfChoose one
Which statement about f(n)=100n2+1000n is false?
Why
f/n2=100+1000/n→100, which is not 0, so f is not o(n2). It is O(n2) (bounded ratio), hence also O(n3) (an O statement may be generous), and f∼100n2.
Check yourselfEnter a number
If f(n)=2n+56n3−n and f∼ln2, what is l?
Why
Leading terms: 6n3/(2n)=3n2, so l=6/2=3. Formally, f/n2=2+5/n6−1/n2→3.
Check yourselfTrue or false?
(2+(−1)n)n=O(n), but there is no l with (2+(−1)n)n∼ln.
Why
True. The ratio to n is 1,3,1,3,…: bounded by 3, so O(n), but it has no limit, so no ∼ statement holds. O only needs a bound; ∼ needs a limiting ratio.
Hardy’s language
Summary
Summary
f=O(ϕ): ∣f/ϕ∣ eventually bounded. f=o(ϕ): f/ϕ→0. f∼lϕ: f/ϕ→l=0.
O(1) means bounded, o(1) means tending to 0. Only the eventual behaviour counts.
o implies O, not conversely; the equals sign is one-way.
Rules: O+O=O, O⋅O=O, O⋅o=o, and adding o(ϕ) does not change f∼ϕ.
A ratio of polynomials is ∼ (ratio of leading coefficients) ×ndifference of degrees.