Massachusetts Institute of Technology Handout 33 6.042J/18.062J: Mathematics for Computer Science October 15, 1998 Professors Nancy Lynch and Srinivas Devadas

The Asymptotic Cheat Sheet

1 Notation

Asymptotic notation consists of six funny symbols used to describe the relative growth rates of functions. These six symbols are defined in the table below.

f = Θ(g) f grows at the same rate as g There exists an n_{0} and constants c_{1}, c_{2} > 0 such that for all n > n_{0}, c_{1}g(n) ≤ f(n) ≤ c_{2}g(n).

f = O(g) f grows no faster than g There exists an n_{0} and a constant c > 0 such that for all n > n_{0}, f(n) ≤ cg(n).

f = Ω(g) f grows at least as fast as g There exists an n_{0} and a constant c > 0 such that for all n > n_{0}, cg(n) ≤ f(n).

f ∼ g f/g approaches 1  lim_{n→∞} f(n)/g(n) = 1

f = o(g) f grows slower than g For all c > 0, there exists an n_{0} such that for all n > n_{0}, f(n) ≤ cg(n).

f = ω(g) f grows faster than g For all c > 0, there exists an n_{0} such that for all n > n_{0}, cg(n) ≤ f(n).

Some sources define these notations a little differently, but these differences rarely matter. The ∼ and Θ notations are confusingly similar; qualitatively, functions related by ∼ must be even more nearly alike then functions related by Θ. The ω notation makes the table nice and symmetric, but is never used in practice. Some asymptotic relationships between functions imply other relationships. These implications follow from the definitions in the table above. Some are listed below.

f = O(g) and f = Ω(g) ⇔ f = Θ(g)
f = O(g) ⇔ g = Ω(f)
f = o(g) ⇔ g = ω(f)
f = o(g) ⇒ f = O(g)
f = ω(g) ⇒ f = Ω(g)
f ∼ g ⇒ f = Θ(g)

2 The Limit Method

The easiest way to prove that an asymptotic relationship holds between two functions is to look at the limit of the ratio. The table below translates facts about the limit of f/g into facts about the asymptotic relationship between f and g. These rules follow from the definitions of the various asympototic notations and from the definition of a limit. All limits below are taken as n → ∞.

lim f(n)/g(n) ≠ 0, ∞ ⇒ f = Θ(g) lim f(n)/g(n) = 1 ⇔ f ∼ g
lim f(n)/g(n) ≠ ∞ ⇒ f = O(g) lim f(n)/g(n) = 0 ⇒ f = o(g)
lim f(n)/g(n) ≠ 0 ⇒ f = Ω(g)  lim f(n)/g(n) = ∞ ⇒ f = ω(g)

In theory, the limit of f/g might reveal nothing about the asympototic relationship between f and g, because the limit might not exist. But in practice, the only difficulty with the limit approach to determining asymptotic relationships is that you have to evaluate some tricky limits. Two theorems make this job managable in most cases.

Theorem 1.

lim_{n→∞} f(n) + g(n) = lim_{n→∞} f(n) + lim_{n→∞} g(n)
lim_{n→∞} f(n) · g(n) = lim_{n→∞} f(n) · lim_{n→∞} g(n)

Theorem 2. (L’Hopital’s Rule)

If lim_{n→∞} f(n) = ∞ and lim_{n→∞} g(n) = ∞, then lim_{n→∞} \frac{f(n)}{g(n)} = lim_{n→∞} \frac{f′(n)}{g′(n)}.

If f grows, say, three times faster than g, then eventually f should be around three times larger than g. This is the intuition for why f′(n)/g′(n) = 3 should imply that f(n)/g(n) = 3 in the limit.

Example. Prove that log^{2} n = o(\sqrt{n}).

lim_{n→∞} \frac{log^{2} n}{\sqrt{n}} = ( lim_{n→∞} \frac{log n}{n^{1/4}})^{2}
= ( lim_{n→∞} \frac{\frac{1}{n}}{\frac{1}{4}n^{−3/4}} )^{2}
= ( lim_{n→∞} \frac{4}{n^{1/4}} )^{2}
= 0

The first step uses the second part of Theorem 1, the second step uses Theorem 2, the third step is simplification, and the final step is evaluation of an easy limit.