CSC165H1, Winter 2021 CSC165H1: Worksheet 11—Introduction to Big-Oh Notation (Partial Solutions)
Learning Objectives
By the end of this worksheet, you will:
• Prove and disprove statements using the definition of Big-Oh.
• Investigate properties of Big-Oh for some common families of functions.
Note: In Big-Oh expressions, it will be convenient to just write down the “body” of the functions rather than
defining named functions all the time. We’ll always use the variable n to represent the function input, and so when
we write “n ∈ O(n2),” we really mean “the functions defined as f(n) = n and g(n) = n2 satisfy f ∈ O(g).”
As a reminder, here is the formal definition of Big-Oh:
g ∈ O(f) : ∃c, n0 ∈ R+, ∀n ∈ N, n ≥ n0⇒ g(n) ≤ cf(n) where f, g : N→ R≥0
1. Comparing polynomials. Our first step in comparing different families of functions is looking at different powers
of n. Consider the following statement, which generalizes the fact that n ∈ O(n2):
∀a, b ∈ R+, a ≤ b⇒ na ∈ O(nb)
(a) Rewrite the above statement by expanding the definition of Big-Oh.
Solution
∀a, b ∈ R+, a ≤ b⇒
(
∃c, n0 ∈ R+, ∀n ∈ N, n ≥ n0⇒ na ≤ cnb
)
(b) Prove the above statement. Hint: you can actually pick c and n0 to both be 1. Even though this is pretty
simple, take the time to write the formal proof as a good warm-up for the rest of this worksheet.
Solution
Proof. Let a, b ∈ R+, and assume a ≤ b. Let c = 1 and n0 = 1. Let n ∈ N, and assume that n ≥ n0. We
want to prove that na ≤ nb.
We can start with our assumption that a ≤ b and calculate:
a ≤ b
na ≤ nb (since n ≥ 1)
na ≤ cnb (since c = 1)
Note: going from a ≤ b to na ≤ nb involves raising n to the power of both sides. This is valid when n ≥ 1.
2. Comparing logarithms. One slight oddity about the definition of Big-Oh is that it treats all logarithmic functions
“the same”. Your task in this question is to investigate this by proving the following statement:1
∀a, b ∈ R+, a > 1 ∧ b > 1⇒ loga n ∈ O(logb n)
We won’t ask you to expand the definition of Big-Oh, but if you aren’t quite sure, then we highly recommend doing
so before attempting even your rough work!
Hint: use the “change of base rule” for logarithms.
1If you are concerned by the fact that logn is not defined at n = 0, you can replace loga n with loga(1 + n) in the above, and
similarly with logb. We usually don’t worry about this subtlety, since our concern is with the value of the functions for larger values of
n. Picking an n0 > 0 avoids the evaluation worry.
Page 1/3
CSC165H1, Winter 2021 CSC165H1: Worksheet 11—Introduction to Big-Oh Notation (Partial Solutions)
Solution
Proof. Let a, b ∈ R+. Assume that a > 1 and b > 1. Let n0 = 1, and let c = 1
logb a
.∗ Let n ∈ N, and assume
that n ≥ n0. We want to show that loga n ≤ c · logb n.
The logarithm change of base rule tells us the following:†
∀a, b, x ∈ R+, a 6= 1 ∧ b 6= 1⇒ loga x =
logb x
logb a
Using this rule, we can write:
loga n =
logb n
logb a
=
1
logb a
logb n
= c · logb n
Since we’ve proved that loga n = c · log bn, we can conclude that loga n ≤ c · logb n.
[Note: we didn’t need to use the assumption that n ≥ 1 in this proof.]
∗Since a, b > 1, we know that c > 0.
†When the bases are equal to 1, loga x is undefined when x 6= 1.
Page 2/3
CSC165H1, Winter 2021 CSC165H1: Worksheet 11—Introduction to Big-Oh Notation (Partial Solutions)
3. Sum of functions. Now let’s look at one of the most important properties of Big-Oh: how it behaves when adding
functions together. Let f, g : N→ R≥0. We define the sum of f and g as the function f + g : N→ R≥0 such that
∀n ∈ N, (f + g)(n) = f(n) + g(n). For example, if f(n) = 2n and g(n) = n2 + 3, then (f + g)(n) = 2n + n2 + 3.
Consider the following statement:
∀f, g : N→ R≥0, g ∈ O(f)⇒ f + g ∈ O(f)
In other words, if g is Big-Oh of f , then f + g is no bigger than just f itself, asymptotically speaking.
Your task for this question is to prove this statement. Keep in mind this is an implication: you’re going to assume
that g ∈ O(f), and you want to prove that f + g ∈ O(f). It will likely be helpful to write out the full statement
(with the definition of Big-Oh expanded), and use subscripts to help keep track of the variables.
Solution
Here’s the full statement, with the definitions expanded:
∀f, g : N→ R≥0,
(
∃c, n0 ∈ R+, ∀n ∈ N, n ≥ n0⇒ g(n) ≤ cf(n)
)
⇒(
∃c1, n1 ∈ R+, ∀n ∈ N, n ≥ n1⇒ f(n) + g(n) ≤ c1f(n)
)
Proof. Let f, g : N→ R≥0. Assume that g ∈ O(f), i.e., there exist n0, c ∈ R+ such that for all natural numbers
n, if n ≥ n0 then g(n) ≤ cf(n). We want to prove that f + g ∈ O(f).
Let n1 = n0, and c1 = c+1. Let n ∈ N, and assume that n ≥ n1. We want to prove that f(n)+g(n) ≤ c1f(n).
Since n ≥ n1 = n0, by our assumption we know that g(n) ≤ cf(n). So then:
g(n) ≤ cf(n)
f(n) + g(n) ≤ f(n) + cf(n)
f(n) + g(n) ≤ (c + 1)f(n)
f(n) + g(n) ≤ c1f(n)
Page 3/3



























































































学霸联盟