Week 5 – Properties of Asymptotic Notation
This document contains a list of some useful properties of
asymptotic notation. You will be using an identical list in
Assignment 4.
You can use these properties to decide whether a given statement
involving asymptotic notation is true or false.
However, remember that if you are asked to prove a statement
from the defnitions, you should use only the formal defnitions of
asymptotic notation and not any of these properties (unless you
prove them!).
In these statements, a, b and c are constants (i.e., they are not
functions of n), and f , g, h, f1, f2, g1 and g2 are functions that
map Z+ → R+.
1 / 7
Week 5 – Properties of Asymptotic Notation
Group 1: the hierarchy summarized
For all constants a > 0 and b > 0:
(1.1) if a > 1, then 1 ∈ o(loga(n))
(1.2) if a > 1, then loga(n) ∈ o(nb)
(1.3) if a < b, then na ∈ o(nb)
(1.4) if b > 1, then na ∈ o(bn)
(1.5) if 1 < a < b, then an ∈ o(bn)
(1.6) an ∈ o(n!)
2 / 7
Week 5 – Properties of Asymptotic Notation
Group 2: transitivity
(2.1) if f ∈ O(g) and g ∈ O(h), then f ∈ O(h)
(compare with (x ≤ y) ∧ (y ≤ z) ⇒ (x ≤ z))
(2.2) if f ∈ Ω(g) and g ∈ Ω(h), then f ∈ Ω(h)
(compare with (x ≥ y) ∧ (y ≥ z) ⇒ (x ≥ z))
(2.3) if f ∈ o(g) and g ∈ o(h), then f ∈ o(h)
(compare with (x < y) ∧ (y < z) ⇒ (x < z))
(2.4) if f ∈ ω(g) and g ∈ ω(h), then f ∈ ω(h)
(compare with (x > y) ∧ (y > z) ⇒ (x > z))
3 / 7
Week 5 – Properties of Asymptotic Notation
Group 3: conditionals and biconditionals
(3.1) f ∈ Θ(g) if and only if f ∈ O(g) and f ∈ Ω(g)
(compare with (x = y) ⇔ ((x ≤ y) ∧ (x ≥ y)))
(3.2) f ∈ O(g) if and only if g ∈ Ω(f )
(compare with (x ≤ y) ⇔ (y ≥ x))
(3.3) f ∈ o(g) if and only if g ∈ ω(f )
(compare with (x < y) ⇔ (y > x))
(3.4) if f ∈ o(g), then f ∈ O(g)
(compare with (x < y) ⇒ (x ≤ y))
(3.5) if f ∈ ω(g), then f ∈ Ω(g)
(compare with (x > y) ⇒ (x ≥ y))
4 / 7
Week 5 – Properties of Asymptotic Notation
Group 3: conditionals and biconditionals (cont’d)
(3.6) If f ∈ o(g), then f ∈/ Ω(g)
(compare with x < y ⇒ x ̸≥ y)
(3.7) If f ∈ ω(g), then f ∈/ O(g)
(compare with x > y ⇒ x ̸≤ y)
Note that the converses of (3.6) and (3.7) are not true for
functions, even if their counterparts are true for real numbers!
5 / 7
Week 5 – Properties of Asymptotic Notation
Group 4: addition
(4.1) if f ∈ O(h) and g ∈ O(h), then f + g ∈ O(h)
(4.2) if f ∈ Ω(h), then f + g ∈ Ω(h)
(4.3) if f ∈ o(h) and g ∈ o(h), then f + g ∈ o(h)
(4.4) if f ∈ ω(h), then f + g ∈ ω(h)
6 / 7
Week 5 – Properties of Asymptotic Notation
Group 5: multiplication
(5.1) for any constant c > 0, cf ∈ Θ(f )
(5.2) if f1 ∈ O(g1) and f2 ∈ O(g2) then f1f2 ∈ O(g1g2)
(5.3) if f1 ∈ Ω(g1) and f2 ∈ Ω(g2) then f1f2 ∈ Ω(g1g2)
(5.4) if f1 ∈ o(g1) and f2 ∈ o(g2) then f1f2 ∈ o(g1g2)
(5.5) if f1 ∈ ω(g1) and f2 ∈ ω(g2) then f1f2 ∈ ω(g1g2)
7 / 7